Erdoes #642 - working report - Erdős Problem a Day

Erdős problem 642 — wave w004

Access date: 2026-07-28 UTC.

Claim labels used throughout:

(a) elementary-rigorous: proved here without an external theorem.
(b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the explicitly named published result.
(c) plausible/structural-unverified: not promoted to a theorem here.
(d) computational-only: exactly what the retained program certifies, but not a hand proof.

Outcome

(b) I obtain the genuine sharpening

f(n)=O\!\left(n(\log n)^7\right),

by rechecking the final parameter layer of Draganić–Methuku–Munhá Correia–Sudakov (DMMS). The published result is \(O(n(\log n)^8)\). The live-page comment suggesting the saving did not explicitly check the last union bound; below I reduce the entire last stage to two inequalities and verify that the seventh-power hypothesis supplies both, including that union bound. This is progress on the open problem, not a solution of the requested \(O(n)\) bound.

Step 0: authoritative live page

I loaded the live page, its LaTeX view, discussion thread, proof-claim thread, and history through the Bright Data browser route rather than datacenter curl.

(b, modulo the live page) At access time the status was OPEN, with the site description “This is open, and cannot be resolved with a finite computation.” It listed 0 claimed proofs, Currently working: None, and Interested in collaborating: None. Thus the mandatory stop condition did not trigger. The page said it was last edited 28 January 2026.

The exact current statement is:

Let \(f(n)\) be the maximal number of edges in a graph on \(n\) vertices such that all cycles have more vertices than chords. Is it true that \(f(n)\ll n\)?

(b, modulo the live page) The accompanying definition says that a chord is an edge between two nonconsecutive vertices of the cycle. The page calls this a problem of Hamburger and Szegedy and cites:

Chen–Erdős–Staton (CES), \(f(n)\ll n^{3/2}\).
Draganić–Methuku–Munhá Correia–Sudakov (DMMS), \(f(n)\ll n(\log n)^8\).

The live discussion had exactly three visible comments:

(c, as posted) AronBhalla, 12 May 2026: a long, explicitly AI-assisted sketch saying the DMMS final parameter check appears to work from average degree \(C(\log n)^7\), hence suggesting \(f(n)\ll n(\log n)^7\). It had one “needs update” reaction and was not a claimed proof.
(c except where independently checked below) BorisAlexeev, 28 January 2026: \(f(5)=9\), \(f(n)=3n-7\) for \(6\le n\le12\), and uniqueness of \(K_{1,2,n-3}\) for \(7\le n\le12\), with more than one extremal graph at \(n=6\). The retained checker independently verifies only the values through \(n=7\), not the asserted \(8\le n\le12\) range or uniqueness.
(a) TerenceTao, 12 January 2026: clarification that a chord must actually be an edge of the graph; a missing edge between nonconsecutive cycle vertices is not a chord. The site says it incorporated this clarification.

Primary-source literature check

(b, bibliographic facts modulo the linked primary sources) I verified that the named papers and identifiers exist:

P. Erdős, “Some recent problems and results in graph theory”00044-1), Discrete Mathematics 164 (1997), 81–85, is the page's original source [Er97d,p.84].
G. Chen, P. Erdős, W. Staton, “Proof of a conjecture of Bollobás on nested cycles”, JCTB 66 (1996), 38–43, is [CES96].
N. Draganić, A. Methuku, D. Munhá Correia, B. Sudakov, “Cycles with many chords”, Random Structures & Algorithms 65 (2024), 3–16, DOI 10.1002/rsa.21207, is [DMMS24]. Its Theorem 1.1 says that \(n(\log n)^8\) edges suffice for large \(n\), and its conclusion explicitly says the authors did not optimize logarithmic powers.
D. Chakraborti, O. Janzer, A. Methuku, R. Montgomery, “Edge-disjoint cycles with the same vertex set”, Advances in Mathematics 469 (2025), 110228, proves a related \(n(\log n)^t\) result with a much larger fixed exponent. Two edge-disjoint cycles on the same vertex set imply a cycle with at least as many chords as vertices, but this does not improve DMMS.
N. Draganić, A. Girão, “Cycles with almost linearly many chords”, arXiv:2601.08769v1 (13 January 2026), proves that sufficiently large constant minimum degree forces a cycle of length \(\ell\) with \(\Omega(\ell/\log^c\ell)\) chords. Its introduction still identifies \((\log n)^8\) average degree as the best bound for forcing at least \(\ell\) chords, and explicitly says even a fixed positive linear fraction of \(\ell\) remained open.

(c, search miss rather than a theorem) Exact-phrase, title/citation, author-page, and 2025–2026 arXiv searches found no primary source claiming \(f(n)=O(n)\), no superlinear lower bound, and no reviewed seventh-power update. This is an honest search result, not a proof that no such source exists.

Elementary reformulation and construction

(a) If a cycle \(C\) has vertex set \(S\) and length \(s=|S|\), then

\#\{\text{chords of }C\}=e(G[S])-s.

Consequently \(C\) is forbidden precisely when it is a Hamilton cycle of \(G[S]\) and \(e(G[S])\ge2s\). This is the equivalence used by the exact checker.

(a) For every \(n\ge3\), the complete tripartite graph

K_{1,2,n-3}

is admissible and has \(3n-7\) edges. Indeed, write \((a,b,c)\) for the counts of cycle vertices in its three parts. Then \(a\le1\), \(b\le2\), and, because equal-part vertices cannot be consecutive on a multipartite cycle,

c\le a+b\le3.

Thus only finitely many profiles are possible. For each feasible profile,

\[ e(G[V(C)])=ab+ac+bc<2(a+b+c). \]

The largest case is \((a,b,c)=(1,2,3)\): it has six vertices and eleven induced edges, hence five chords, still fewer than six. Therefore

f(n)\ge3n-7.

The verifier exhausts all six feasible profiles independently.

The seventh-power upper bound

What is imported

Let \(L=\log n\). Assume an \(n\)-vertex graph \(G\) has average degree

d(G)\ge C L^7

for a sufficiently large absolute constant \(C\).

(b, DMMS Lemma 2.4) There is a bipartite subgraph \(H\), on \(N\) vertices, which is 100-almost-regular, is a \(1/(10L)\)-expander, and satisfies

d(H)\ge \frac{d(G)}{600L}.

Writing \(\delta=\delta(H)\), 100-almost-regularity gives

\delta\ge \frac{C}{60000}L^6=:aCL^6, \qquad a=\frac1{60000}, \qquad N\ge\delta+1. \tag{1}

(b, DMMS Corollary 2.12 in the published version; Corollary 2.13 in arXiv v1) The mixing time \(k\) can be chosen with

k\le A L^2\log N \tag{2}

for an absolute constant \(A\) (the paper safely takes \(A=10^{10}\)).

The remaining imported ingredients are published Lemma 3.5 and Theorem 3.6 (Theorem 3.7 in arXiv v1), plus their final assembly in Section 3.5. I do not re-prove those probabilistic results.

Exact reduction of every final parameter requirement

DMMS set

\beta=10^{-28}, \qquad t=\frac{\beta^2N}{10^6k}. \tag{3}

(a, direct algebra from the displayed DMMS hypotheses) Every degree-side requirement in the final assembly follows from

\delta>B_\delta k^2, \tag{4}

where it is enough to take

B_\delta= \max\left\{ \frac{10^3}{\beta}, \frac{5\cdot10^{23}}{\beta^2}, \frac{5\cdot10^{39}}{\beta^2} \right\}.

The three terms respectively cover:

the self-avoiding-walk theorem's \(\delta\ge10^3k^2/\beta\);
\(t/5\ge10^{17}kN/\delta\), which is equivalent to

\(\delta\ge5\cdot10^{23}\beta^{-2}k^2\);

the last chord count

\[ \frac{(t/5)^2\delta}{10^{32}k^2N}>\frac{2t}{k}, \] which is equivalent to \(\delta>5\cdot10^{39}\beta^{-2}k^2\).

The fixed lower-degree hypotheses such as \(\delta\ge10^8\) then follow for sufficiently large \(n\).

(a, direct algebra from the displayed DMMS hypotheses) Every order-side requirement follows from

N>B_Nk^2\log N, \tag{5}

where it is enough to take

B_N=\frac{5\cdot10^{31}}{\beta^2}.

Indeed, \(t/5\ge10^{25}k\log N\) is exactly (5) with this constant.

There is one more condition hidden in the paper's last union-bound sentence and not explicitly checked in the live comment:

k\exp\!\left(-\frac{t}{10^{25}k}\right) \le \exp\!\left(-\frac{t}{10^{26}k}\right). \tag{6}

Taking logarithms, (6) follows if

\log k\le 9\cdot10^{-26}\frac{t}{k}.

Condition (5) implies \(N>k\), hence \(\log k\le\log N\), and with (3) its right side is at least

9\cdot10^{-26}\frac{\beta^2}{10^6}B_N\log N =4.5\log N.

Thus (5) also rigorously supplies the omitted union-bound check.

Why \(C L^7\) supplies the two master inequalities

(a) From (1), (2), and \(\log N\le L\),

\frac{\delta}{k^2} \ge \frac{aCL^6}{A^2L^4(\log N)^2} \ge \frac{aC}{A^2}.

Choose the absolute constant \(C\) so that \(aC/A^2>B_\delta\). This proves (4), uniformly in the unknown size \(N\) of the cleaned subgraph.

(a) For (5),

\frac{N}{k^2\log N} \ge \frac{N}{A^2L^4(\log N)^3}. \tag{7}

The function \(x/(\log x)^3\) is increasing for all sufficiently large \(x\). Since \(N\ge aCL^6\), the right side of (7) is at least

\frac{aCL^6}{A^2L^4\{\log(aCL^6)\}^3} = \frac{aC}{A^2}\, \frac{L^2}{\{\log(aCL^6)\}^3} \longrightarrow\infty.

It therefore exceeds the fixed \(B_N\) for all sufficiently large \(n\). This proves (5) without assuming whether \(N\) is polylogarithmic or close to \(n\).

(b, conclusion modulo the named DMMS lemmas) Conditions (4) and (5) validate every application of DMMS Lemma 3.5 and Theorem 3.6, the chord-count comparison, the closing-edge estimate, and the final union bound. Their Section 3.5 now runs unchanged and produces a cycle with at least as many chords as vertices from average degree \(C(\log n)^7\). Converting average degree to edges and enlarging the constant for finitely many small \(n\) yields

\boxed{f(n)=O(n(\log n)^7)}.

This proof also identifies the exact wall of this version of the machinery. (a) In the worst case \(\log N\asymp L\), (2) permits \(k^2\asymp L^6\); after the cleaning loss, starting degree \(L^p\) gives only \(\delta\asymp L^{p-1}\). The indispensable condition \(\delta\gg k^2\) therefore forces \(p\ge7\). Saving another full logarithm requires a stronger cleaning/mixing statement or a different self-avoidance argument; retuning the same final constants cannot do it.

Independent computation

The standalone verifier is runs/erdos642_wavew004_verify.py; it uses only the Python standard library. Run:

python3 runs/erdos642_wavew004_verify.py

(d) It exhausts all labelled graphs in the only edge ranges that could beat the displayed witnesses and obtains

\begin{array}{c|rrrrrrr} n&1&2&3&4&5&6&7\\ \hline f(n)&0&1&3&6&9&11&14. \end{array}

It checks 82,737 dense labelled graphs, using an independent Held–Karp Hamilton-cycle test on every vertex subset with at least twice as many induced edges as vertices.

(d) It also recomputes the master constants

B_\delta=5\cdot10^{95}, \qquad B_N=5\cdot10^{87},

checks all rearrangements involving \(t,\beta,k,N,\delta\), checks the union-bound exponent, and gives a deliberately crude numerical sanity witness \(C=10^{130}\) for the displayed constant inequalities once the named lemmas' own “sufficiently large” thresholds are passed. This is not advertised as an explicit global constant because the imported lemmas do not make all of their \(n_0\) thresholds explicit.

Recorded output:

PASS uniform K_{1,2,n-3} cycle profiles (6 profiles)
PASS exhaustive f(1)=0
PASS exhaustive f(2)=1
PASS exhaustive f(3)=3
PASS exhaustive f(4)=6
PASS exhaustive f(5)=9
PASS exhaustive f(6)=11
PASS exhaustive f(7)=14
PASS exhaustive dense labelled graphs checked: 82737
PASS B_delta = 500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
PASS B_size  = 5000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
PASS a*C/A^2 = 1.666667e+105 > B_delta
PASS worst-case N/(k^2 log N) lower bound at L=1000: 1.547570e+103 > B_size
PASS final union-bound arithmetic
ALL CHECKS PASSED

(d) A bounded exploratory \(n=13\) lazy-cut search was inconclusive: it produced neither an admissible 33-edge graph nor an infeasibility certificate. No \(n=13\) claim is made, and no solver trace is being mistaken for a theorem.

PARTIAL: Rigorous modulo the published DMMS lemmas, the final parameter argument improves the known upper bound to f(n)=O(n(log n)^7); the independent checker passes the construction, f(n) through 7, all constant rearrangements, and the previously omitted union bound.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger