# Turán number of a finite family.

 Importance: Medium ✭✭
 Author(s): Erdos, Paul Simonovits, Miklos
 Subject: Graph Theory
 Keywords:
 Posted by: fhavet on: March 5th, 2013

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.

Conjecture   For every finite family of graphs there exists an such that .

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:

Conjecture   For all integers there exists a positive c = c(\ell) such that every -free graph has a -free subgraph with .

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.