Turán number of a finite family.

Importance: Medium ✭✭
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 5th, 2013

Given a finite family ${\cal F}$ of graphs and an integer $n$, the Turán number $ex(n,{\cal F})$ of ${\cal F}$ is the largest integer $m$ such that there exists a graph on $n$ vertices with $m$ edges which contains no member of ${\cal F}$ as a subgraph.

\begin{conjecture} For every finite family ${\cal F}$ of graphs there exists an $F\in {\cal F}$ such that $ex(n, F ) = O(ex(n, {\cal F}))$ .% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

For the case when ${\cal F}$ consists of even cycles, this would mean that (up to constants) the Turán number of ${\cal F}$ is given by that of the longest cycle in ${\cal F}$. Verstraëte (see [KO]) conjectured something stronger: \begin{conjecture} For all integers $k < \ell$ there exists a positive c = c(\ell) such that every $C_{2\ell}$-free graph $G$ has a $C_{2k}$-free subgraph $H$ with $e(H) ≥ e(G)/c$. \end{conjecture}

This conjecture was motivated by a result of Györi [G] who showed that every bipartite $C_6$-free graph $G$ has a $C_4$-free subgraph which contains at least half of the edges of $G$. The case $k=2$ was proved in [KO].

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Bibliography

*[ES] P.Erdös and M. Simonovits, Compactness results in extremal graph theory, Combinatorica 2 (1982), 275–288.

[KO] D. Kühn and D. Osthus, 4-cycles in graphs without a given even cycle, J. Graph Theory 48 (2005), 147-156.

[G] E. Györi, $C_6$-free bipartite graphs and product representation of squares, Discrete Math. 165/166 (1997), 371-375.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)


* indicates original appearance(s) of problem.