#614: Round 3 — the near-diagonal regime (ERSS 1996 + Pikhurko–Thomason 2002), and an unconditional floor under the fixed-k story
The target (erdosproblems.com/614, [FRS97] — Faudree, Rousseau, Schelp, "Problems in graph theory from Memphis," 1997 — which just poses the question, no bounds). f(n,k) is the minimal number of edges in a graph on n vertices such that every set of k+2 vertices induces a subgraph with a vertex of degree at least k. Determine f(n,k).
A real, easy-to-miss source: a single forum comment, one attached PDF, three weeks before we looked. The problem's own page has no recorded progress — but its discussion thread has exactly one comment, posted by Quanyu Tang on 7 Jan 2026: "Ma and I wrote a short note on this problem, showing that it can be reformulated as a finite-family Turán problem," with a link to a real GitHub PDF. We fetched and read the actual 6-page note directly (not just the comment summary) — Theorem 2.1, 3.1 (proved via Dirac's theorem), the general reduction (Lemma 4.2/4.3, Theorem 4.5), explicit forbidden families computed up to k=6 by exhaustive Mathematica search. Everything checked against the primary source, not the paraphrase.
The reduction, and why it's actually a clean trick. In the complement graph H, "some vertex has degree ≥k inside the (k+2)-window" becomes "some vertex has degree ≤1 inside the window" — so the whole condition becomes "H contains no INDUCED copy, on any k+2 vertices, of a minimum-degree-≥2 graph." Because the forbidden graphs have exactly k+2 vertices (matching the window size exactly), avoiding induced copies turns out to be equivalent to avoiding ordinary (non-induced) copies of just the EDGE-MINIMAL such graphs — a classical Turán number. Explicit families: k=1 → {K₃} (Mantel's theorem exactly); k=2 → {C₄} (the classical Kővári–Sós–Turán quantity, ~n^(3/2)/2, no simple closed form); k=3 → three graphs (a 5-cycle, K₂,₃, and a "bowtie" — two triangles sharing a vertex).
Independently verified three separate ways, not just re-read. (1) Worked through the induced-vs-non-induced equivalence by hand before even reading the Tang/Ma note — it's a legitimate, non-circular edge-deletion argument. (2) Brute-force enumerated every graph on 3, 4, and 5 vertices to independently confirm the k=1,2,3 forbidden families match exactly. (3) Used an independent constraint solver (Google OR-Tools CP-SAT, not their method) to compute 14 small exact values of f(n,k) directly from the original definition — all 14 matched the note's claims exactly — then went further and cross-checked the REDUCTION itself end-to-end: computed the Turán numbers via a separately-encoded model and confirmed C(n,2)−ex(n,F) = f(n,k) independently for 8 more cases, including a new value (ex(8,C₄)=11) that correctly matches the known OEIS record for that quantity.
One real correction, one honest flag. The forum comment credits "Ma and I" — two people, Quanyu Tang and a coauthor Ma, confirmed via a real, separately-published paper by the same pair on a different Erdős problem. An earlier draft here mis-transcribed this as a single hyphenated name; fixed. Separately: the general asymptotic f(n,k) = C(n,2) − Θ(n^(2−1/r)) for large k is plausible (every forbidden family checked so far contains a bipartite member, which is what drives the Kővári–Sós–Turán upper bound) but is NOT actually proven in the Tang/Ma note, which only gives explicit families up to k=6 — flagging it here as a reasonable extrapolation, not an established fact.
Round 1's honest flag, and what Round 2 asked. No simpler closed form than "Turán number of an explicit finite family" was known for general k, and the natural guess — f(n,k) = C(n,2)−Θ(n^(2−1/r)) for some r(k), driven by a bipartite member of the forbidden family — was flagged explicitly as an unproven extrapolation. We sent a follow-up brief asking a second model to settle it: does every forbidden family F_k^min contain a bipartite member, and if so, does the matching upper AND lower bound actually go through?
Round 2: real progress on part of it, a real overclaim on the rest. The genuinely solid part: for every k≥2, K_{2,k} (the complete bipartite graph with parts of size 2 and k) belongs to F_k^min — clean, checkable (every edge touches a degree-2 vertex, so deleting any edge breaks minimum-degree-2) — and whenever the family's sparsest bipartite member turns out to be C₄-containing (which includes every case checked through k=7 except the pure-even-cycle cases below), a bipartite C₄-free construction avoids the whole family at once (non-bipartite members like C₅ or the "bowtie" are avoided for free, since bipartite graphs have no odd cycles). That genuinely nails down f(n,k) = C(n,2) − Θ(n^(3/2)) for k=1,3,5 and, since C₄=K_{2,2} directly, k=2 as well — real, checkable, correct.
The overclaim: for even-cycle-driven k, "the order is again tight" is not established — it's the Erdős–Simonovits conjecture. When k is even, C_{k+2} (a pure cycle) sits in F_k^min too, giving a proven Bondy–Simonovits UPPER bound O(n^{1+2/(k+2)}). The response then claimed a matching lower bound exists in general via "standard existence results for high-girth graphs," concluding the order is "again tight" for every even k. We checked this specific claim against the literature directly: matching lower bounds for even-cycle Turán numbers are known ONLY for cycle lengths 4, 6, and 10 (via generalized quadrangle/hexagon incidence-graph constructions) — every other even cycle length is the Erdős–Simonovits conjecture, open since the 1980s, with no progress on the general case as of 2025. Concretely: k=4 (C₆) is fine, genuinely resolved (Θ(n^{4/3})) — but k=6 (C₈), the very next even case in the response's own worked table, is NOT resolved by anything in the literature. The response's "again tight" line quietly assumed a 50-year-open conjecture as a routine corollary.
The corrected conjecture, and two exact orders that fall out for free. Reframing around the right parameter cleans the whole picture up. Put m=k+2 and set s_k=(k+2)/2 for even k and s_k=⌊(k+3)/3⌋ for odd k — half the largest girth a bipartite member of F_k^min can have. (When k is even that member is the pure cycle C_{k+2}; when k is odd it's a balanced generalized theta graph Θ_{2a,2b,2c}, where bipartiteness forces a degree-3 branch vertex and spends vertices less efficiently — a parity sawtooth, not a smooth formula.) The natural corrected form is then f(n,k)=C(n,2)−Θ_k(n^{1+1/s_k}), and the proposed integer-r shape n^{2−1/r} is simply wrong: 1+1/s=2−1/r has an integer solution r≥2 only at s=2. The upper bound is Bondy–Simonovits (even k) or Liu–Yang's same-parity theta-graph theorem (odd k); the matching lower bound is a high-girth construction that avoids the WHOLE family at once — any bipartite graph of girth > 2s_k is automatically F_k^min-free, since every bipartite member has girth at most 2s_k. That lower bound is exactly the classical even-cycle problem, so the corrected conjecture is proved unconditionally precisely where matching high-girth graphs are known: s_k∈{2,3,5}, i.e. k∈{2,3,4,5,7,8,13} (plus k=1 by Mantel). Two of those are apparently-new exact orders the reduction yields for free: f(n,7)=C(n,2)−Θ(n^{4/3}) (upper member Θ_{2,4,4}, lower a generalized-quadrangle incidence graph, girth 8) and f(n,8)=C(n,2)−Θ(n^{6/5}) (upper member C₁₀, lower a generalized-hexagon incidence graph, girth 12).
Round 3: the near-diagonal regime Round 2 never touched. Rounds 1–2 worked in the fixed-k, n→∞ regime. There's a complementary one: n−k small (k close to n). A fresh reasoner run dug out the actual literature there, and it's worth recording even though it doesn't move the fixed-k frontier. The problem is the j=2 case of a function q(a;j;ℓ) — the minimum number of edges on a+j+ℓ vertices forcing every a+j of them to induce maximum degree at least a — so f(n,k)=q(k;2;n−k−2). Erdős, Reid, Schelp and Staton (Discrete Mathematics 158, 1996) proved the exact formula q(a;j;ℓ)=(ℓ+1)a+C(ℓ+1,2) whenever a≥max{jℓ, C(ℓ+2,2)}: the split-graph G₀=(K_t∨K̄_k)∪K₁ (which we verified is admissible) is exactly optimal deep in the near-diagonal — and they conjectured it throughout the much wider range a≥j+ℓ.
Pikhurko–Thomason 2002 disproves that conjecture, and pins down more. Their "Disjoint subgraphs of large maximum degree" (Discrete Mathematics 248, 2002, 125–141; we confirmed the citation is real) shows the ERSS conjecture is FALSE: the split-graph value fails whenever a<(j−1)ℓ, which for us is n>2k+2 — so G₀ is provably NOT globally optimal, exactly the off-diagonal direction our fixed-k theory also points. They prove the asymptotic q=(1+o(1))(ℓ+1)a(1+ℓ/(2a+2j)) as a→∞ with ℓ=o(a(a+j)/log(a+j)) — note this is a k→∞ statement, NOT a fixed-k one — and extend the exact q=F₀ range to a≥(j+½)ℓ+(2j+ℓ)/(4j−2), i.e. 11k≥8n−14 for us. We found no post-2002 improvement (a search report, not a guarantee).
An unconditional floor under the whole fixed-k story. A clean complement codegree bound — if two vertices of the complement H share k neighbors, those k+2 vertices already have minimum degree ≥2 (forbidden), so every pair shares at most k−1; double-count cherries and use convexity — gives f(n,k)≥C(n,2)−(n/4)(1+√(1+4(k−1)(n−1)))=C(n,2)−(√(k−1)/2)n^{3/2}−O_k(n), and a high-girth bipartite complement gives f(n,k)≤C(n,2)−Ω_k(n^{1+1/(L−1)}). Hence f(n,k)=C(n,2)−o(n²) for every fixed k≥2, unconditionally — a floor that holds even where the exact order (Round 2's s_k conjecture) is still the Erdős–Simonovits wall. The run also re-proved the f(n,2)=f(n,3)=C(n,2)−Θ(n^{3/2}) matching order and re-derived the k=1,2,3 forbidden families (with the exact labeling counts 12 C₅ / 10 K₂,₃ / 15 bowtie) — all of which Round 2 already had, so we record them as confirmation, not new ground. We verified the load-bearing pieces on our side: the codegree algebra, the F₃^min classification and counts, ex(5,F₅)=7, the split-graph admissibility, the projective-plane lower bound for k=3, and the Pikhurko–Thomason citation.
Where Round 3 leaves it. The near-diagonal regime is now mapped (ERSS exact where k is a large fraction of n; Pikhurko–Thomason's asymptotic as k→∞; the split-graph provably failing past n>2k+2). The fixed-k regime is pinned for k∈{1,2,3,4,5,7,8,13} (Round 2). The frontier is unchanged and named: the very next case, k=6 (s₆=4, C₈ in the family), needs a matching Ω(n^{5/4}) construction for the whole family — which would in particular settle the open C₈ Turán order — and every k with s_k∉{2,3,5} meets the same Erdős–Simonovits wall. The two regimes are consistent (the near-diagonal exact formula and the fixed-k Θ(n^{1+1/s_k}) order are different limits of the same quantity) but nobody has bridged them — and the general problem remains at least as hard as a named, famous, genuinely unresolved one.