![](/files/happy5.png)
Turán number of a finite family.
Given a finite family of graphs and an integer
, the Turán number
of
is the largest integer
such that there exists a graph on
vertices with
edges which contains no member of
as a subgraph.
![$ {\cal F} $](/files/tex/f3941009edea56b027602b3a3e226da998b78e0a.png)
![$ F\in {\cal F} $](/files/tex/1b6109e0bcc06d36efed4d6b15e1ff4e529f533c.png)
![$ ex(n, F ) = O(ex(n, {\cal F})) $](/files/tex/05fdebcd6442863bb0866ecaf1c43a1a9eada77c.png)
For the case when consists of even cycles, this would mean that (up to constants) the Turán number of
is given by that of the longest cycle in
. Verstraëte (see [KO]) conjectured something stronger:
![$ k < \ell $](/files/tex/1ea9e20782adf0c1c0ea37c0f116f4894526960d.png)
![$ C_{2\ell} $](/files/tex/6b336999f576e18d9e9116d7f8da32121fe1843a.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ C_{2k} $](/files/tex/1a9e299078a8c1ebdcab6cf14d11118f097f063f.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ e(H) ≥ e(G)/c $](/files/tex/5d7b8e2dedf8adcc75f967ab3497b6ec612d999b.png)
This conjecture was motivated by a result of Györi [G] who showed that every bipartite -free graph
has a
-free subgraph which contains at least half of the edges of
. The case
was proved in [KO].
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, -free bipartite graphs and product representation of squares, Discrete Math. 165/166 (1997), 371-375.
* indicates original appearance(s) of problem.