Originator(s): P. Erdős, R. Faudree, C. Rousseau, and R. Schelp (presented by John Lenz - REGS 2009)
Turán's Theorem implies that if an n-vertex graph (G) has more than (1-1/r) n(n-1)/2 edges, then G has Kr+1 as a subgraph. Erdos, Faudree, Rousseau, and Shelp (see [EFRS]) asked the following question in 1990: Fix &alpha in the interval (0,1], and suppose that every set of αn vertices in G induces more than βn² edges. What is the smallest β (in terms of α and r) that forces G to contain Kr+1?
One can view the question as follows. Let β(α,G) be the minimum, over all vertex subsets S with size αn, of |E(G[S])|/n². In other words, G contains some set of αn vertices that induces at most β(α,G)n² edges. Let β(α,r) be the maximum of β(α,G) over all Kr+1-free graphs G. The problem is then to determine β(α,r).
Conjecture 1 ([EFRS]) β(1/2,2) = 1/50.
Comments: Erdős offered $250 for a solution to Conjecture 1, which is still open. The lower bound is shown by the blowup of C5 or by the blowup of the Peterson graph. (The blowup of a graph expands all vertices into independent sets of the same size.) In the blowup of C5, taking the blowups of two non-adjacent vertices plus half the vertices from the blowup of a neighbor of one of them yields n/2 vertices that span only n²/50 edges. As an upper bound, Krivelevich [K] showed that β(1/2,2) ≤ 1/36. Keevash and Sudakov [KS06] showed β(1/2,G) ≤ 1/50 when G is triangle-free and has at least n²/5 edges or at most n²/12 edges.
Conjecture 2 ([EFRS]). Fix r=2. If 17/30 ≤ α ≤ 1, then β(α,2) = (2α-1)/4. If 53/120 ≤ α ≤ 17/30, then β(α,2) = (5α-2)/25.
Comments: In the higher range, the lower bound comes from Kn/2,n/2 (the blowup of K2); take all of one partite set plus (α-1/2)n vertices from the other part. In the lower range, the lower bound comes from the blowup of C5; this case includes Conjecture 1. [EFRS] proved Conjecture 2 for 0.648 ≤ α ≤ 1 when n is sufficiently large (note that 17/30 < 0.648). This suggested the next conjecture.
Conjecture 3 ([EFRS]) For each positive integer r, there is a constant cr less than 1 such that if cr≤α≤1, then β(α,r)=β(α,Tr), where Tr is the Turán graph. That is, when α is near 1 the extremal example is the Turán graph.
Comments:
Conjecture 3 was proved by Keevash and Sudakov [KS02]. They also proved that in this range of α the Turán graph is the only Kr+1-free graph G with β(α,G)=β(α,r).
In addition to studying β(α,2) and β(α,3), we can study the analogous problem for C4-free graphs. That is, does every C4-free graph have a set of αn vertices that induce at most βn3/2 edges? How small can β be in terms of α?
References:
[EFRS]
Erdos, P, Faudree, R. J., Rousseau, C. C., Schelp, R. H.
A local density condition for triangles.
Discrete Math. 127 (1994), no. 1-3, 153--161.
[KS02]
Keevash, Peter, Sudakov, Benny. Local density in graphs with forbidden
subgraphs. Combin. Probab. Comput. 12 (2003), no. 2, 139--153.
[KS06]
Keevash, Peter, Sudakov, Benny.
Sparse halves in triangle-free graphs.
J. Combin. Theory Ser. B 96 (2006), no. 4, 614--620.
[K]
Krivelevich, Michael.
On the edge distribution in triangle-free graphs.
J. Combin. Theory Ser. B 63 (1995), no. 2, 245--260.