Estimate h(n): largest guaranteed triangle degree-sum above the Turán threshold (Erdős #1033)
Statement
Let $h(n)$ be the largest value such that every graph on $n$ vertices with more than $n^2/4$ edges contains a triangle whose three vertices have degrees (in the whole graph) summing to at least $h(n)$. (By Turán's theorem such a graph always contains at least one triangle.) Estimate $h(n)$. In particular, is it true that $$h(n)\geq \left(2(\sqrt{3}-1)-o(1)\right)n\,?$$
Acceptance. FULLY RESOLVES: determine the asymptotic constant $\lim_{n\to\infty} h(n)/n$ — in particular prove (or disprove) the conjectured $h(n)\geq (2(\sqrt{3}-1)-o(1))n$, closing the gap between the lower bound $\tfrac{21}{16}n$ and the upper bound $2(\sqrt{3}-1)n$ stated in the background — with a complete proof. ADVANCES, any of: (a) improve the best known lower-bound constant strictly above $21/16=1.3125$ (Fan's bound) with proof; (b) improve the upper-bound construction below $2(\sqrt{3}-1)\approx 1.464$ with an explicit graph family; (c) compute exact or near-exact values of $h(n)$ over a range of $n$ by exhaustive search, delivering data that constrains the constant plus the extremal graphs. Deliver the improved-constant proof, or the construction / search code + certificates.
Background
A conjecture of Bollobás and Erdős [Er82e, p.71], [Er93, p.344]; the original question in [Er82e] was whether $h(n)\geq \tfrac{3}{2}n$. The current bounds are $$\tfrac{21}{16}n\leq h(n)\leq 2(\sqrt{3}-1)n+O(1),$$ with $21/16=1.3125$ and $2(\sqrt{3}-1)\approx 1.464$. The upper bound is due to Erdős and Laskar [ErLa85] (whose paper concerns chordal subgraphs — a triangle with all incident edges is chordal); the construction was made explicit by Fan [Fa88]: take a complete bipartite graph between parts of sizes $k=cn$ and $l=n-k$ with $m=\lfloor n^2/4\rfloor+1$ edges, then add $m-kl$ triangle-free edges inside the $k$-part, so every triangle uses two $k$-vertices and one $l$-vertex and has degree sum at most $(c^{-1}+3c-2)n+O(1)$, minimised at $c=1/\sqrt{3}$ to give $2(\sqrt{3}-1)n+O(1)$. The lower bound $\tfrac{21}{16}n$ is due to Fan [Fa88]. More generally, for $\Delta_r(n,m)$ = the largest guaranteed degree sum over $r$-cliques in an $n$-vertex $m$-edge graph, Erdős (see [Fa92]) proved $\Delta_r(n,m)\leq (1-\epsilon)\tfrac{2rm}{n}$ in a mid-range of $m$, and Bollobás and Nikiforov [BoNi05] proved $\Delta_r(n,m)\geq (1-\epsilon)\tfrac{2rm}{n}$ near the Turán threshold $m>t_r(n)-\delta n^2$ (the $r=2$ threshold regime is erdosproblems.com/904). The conjecture is thus that $h(n)=(2(\sqrt{3}-1)+o(1))n$, matching Fan's construction. Listed as open on erdosproblems.com/1033 (fetched 2026-07-13, status 'open', tagged 'graph theory'). Attacker's tool: exhaustive small-$n$ computation of $h(n)$ to test the constant and search for improved lower-bound constructions, plus analytic improvement of Fan's $21/16$ constant.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1033 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.