ERDŐS/DAILY ▸

← back to the ledger

ERDőS #584 · PROVED

Erdős problem #584 — wave9t

Date checked: 2026-07-28 UTC.

Claim labels used throughout:

external mathematical input.

comment, or unaudited preprint claim, not promoted to a theorem here.

computation.

Observations about a live page or the contents of a source are labelled “source check”; that label does not assert that an unrefereed source's mathematics has been certified.

0. Mandatory live-page gate

I fetched https://www.erdosproblems.com/584 through the Bright Data browser route on 2026-07-28. The returned page was the rendered problem page, not a Cloudflare challenge. I also followed its discussion link, which resolved to /forum/thread/584, and read all four comments. I separately fetched the page's LaTeX view to avoid losing exponents in rendered-text extraction.

Verbatim live statement

Let \(G\) be a graph with \(n\) vertices and \(\delta n^{2}\) edges. Are there subgraphs \(H_1,H_2\subseteq G\) such that

- \(H_1\) has \(\gg \delta^3n^2\) edges and every two edges in \(H_1\) are contained in a cycle of length at most \(6\), and furthermore if two edges share a vertex they are on a cycle of length \(4\), and - \(H_2\) has \(\gg \delta^2n^2\) edges and every two edges in \(H_2\) are contained in a cycle of length at most \(8\).

Status and collision markers

claims have been submitted yet.”

Thus the mandatory stop rule was not triggered.

Known results listed on the live page

The page calls this a problem of Erdős, Duke, and Rödl and records:

conclusion when \(n\) is sufficiently large depending on fixed \(\delta\).

challenge.

\(H_1\) conclusion with \(\delta^5\) in place of \(\delta^3\).

conclusion when \(\delta>n^{-1/5}\).

collection entry.

All four comments

The website explicitly warns that comments are user-provided and unverified.

  1. (c; comment/preprint claim) Eric Li, 10 June 2026, links

arXiv:2606.06522. The comment says the preprint proves internal \(C_{\leq 8}\) and weak internal \(C_{\leq 6}\) cores of the requested sizes for \(\rho=e(G)/n^2\geq n^{-1/3}\); gives an ambient-witness strong \(C_6\) result for \(k=o(n^{1/2})\); and gives a random-lift obstruction to the internal strong \(C_6\) version for fixed \(\beta\in[1/3,1/2)\). The comment stresses that the adjacent-edge \(C_4\) condition is convention-sensitive.

  1. (c; comment claim) Przemek Chojecki, 21 April 2026, says that

GPT-5.4 Pro can construct a counterexample to the second assertion “if there's no additional conditions on sparsity” and links erdos584.pdf.

  1. (c; comment claim) Nat Sothanaphan, 21 April 2026, says a

“standard check” found two minor issues in Proposition 4 of that note but that neither affected its Theorem 1, the main counterexample.

  1. (source check) Alfaiz, 24 November 2025, reported that [DuEr83]

did not load a reference; the page now says it was updated to address the comment.

The second comment is not registered in the site's proof-claim system: the live page still explicitly displays “0 claimed proofs.” This report does not treat the comment or its AI-generated note as authority. Instead, it independently reconstructs the counterexample in explicit coordinates, checks finite instances from scratch, and isolates the one classical theorem needed for the infinite family.

1. Main result: the literal \(H_2\) assertion is false

1.1 A general obstruction

Lemma (a). Let \(G\) have girth greater than \(8\). If \(H\subseteq G\) has the property that every two distinct edges of \(H\) lie together on a cycle of length at most \(8\), then \(e(H)\leq1\).

Proof. If \(H\) had distinct edges \(e,f\), the required witness would be a cycle of length at most \(8\) in \(H\), hence in \(G\), contradicting the girth. This argument remains valid under the weaker ambient-witness interpretation, since even \(G\) has no such cycle. \(\square\)

Consequently, any sequence of girth-\(>8\) graphs whose average degrees tend to infinity refutes a uniform lower bound \(e(H_2)\gg\delta^2n^2\), because

\[ \delta^2n^2 =\left(\frac{e(G)}{n^2}\right)^2n^2 =\left(\frac{e(G)}n\right)^2 =\frac{\bar d(G)^2}{4}\longrightarrow\infty. \tag{1} \]

1.2 Explicit coordinate family \(D(5,q)\)

Let \(q\) range over primes and work in \(\mathbb F_q=\mathbb Z/q\mathbb Z\). Define two vertex classes

\[ P=\mathbb F_q^5,\qquad L=\mathbb F_q^5. \]

Write points and lines, respectively, as

\[ p=(p_1,p_{11},p_{12},p_{21},p_{22}),\qquad \ell=[\ell_1,\ell_{11},\ell_{12},\ell_{21},\ell_{22}]. \]

Join \(p\) to \(\ell\) exactly when the following four equations hold in \(\mathbb F_q\):

\[ \begin{aligned} \ell_{11}-p_{11}&=\ell_1p_1,\\ \ell_{12}-p_{12}&=\ell_{11}p_1,\\ \ell_{21}-p_{21}&=\ell_1p_{11},\\ \ell_{22}-p_{22}&=\ell_1p_{12}. \end{aligned} \tag{2} \]

This is precisely the first four incidence relations defining the graph \(D(5,q)\) in Lazebnik--Ustimenko--Woldar.

Counts (a). There are \(q^5\) vertices on each side. Given \(p\) and an arbitrary \(\ell_1\), equations (2) successively determine the unique values

\[ \begin{aligned} \ell_{11}&=p_{11}+\ell_1p_1,\\ \ell_{12}&=p_{12}+\ell_{11}p_1,\\ \ell_{21}&=p_{21}+\ell_1p_{11},\\ \ell_{22}&=p_{22}+\ell_1p_{12}. \end{aligned} \tag{3} \]

Thus every point has degree \(q\). Conversely, given \(\ell\) and \(p_1\), the equations uniquely give

\[ \begin{aligned} p_{11}&=\ell_{11}-\ell_1p_1,\\ p_{12}&=\ell_{12}-\ell_{11}p_1,\\ p_{21}&=\ell_{21}-\ell_1p_{11},\\ p_{22}&=\ell_{22}-\ell_1p_{12}, \end{aligned} \tag{4} \]

so every line also has degree \(q\). The graph is simple and bipartite, and therefore

\[ n_q=2q^5,\qquad e(G_q)=q^6. \tag{5} \]

Girth (b). Proposition 2.1(i),(iii) of F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, A new series of dense graphs of high girth, Bull. Amer. Math. Soc. 32 (1995), 73--79, states that \(D(k,q)\) is a \(q\)-regular bipartite graph of order \(2q^k\), and that for odd \(k\),

\[ g(D(k,q))\geq k+5. \]

Specializing to \(k=5\) gives

\[ g(G_q)=g(D(5,q))\geq10. \tag{6} \]

The arXiv identifier, title, authors, coordinate definition, and exact proposition were checked in the primary paper. Equation (6) is the only non-elementary input in the uniform counterexample.

1.3 Exact density calculation and the uniformity step

From (5),

\[ \delta_q=\frac{e(G_q)}{n_q^2} =\frac{q^6}{(2q^5)^2} =\frac1{4q^4}, \tag{7} \]

and hence

\[ \delta_q^2n_q^2 =\frac1{16q^8}\,4q^{10} =\frac{q^2}{4}. \tag{8} \]

Equivalently,

\[ e(G_q)=2^{-6/5}n_q^{6/5},\qquad \delta_q=2^{-6/5}n_q^{-4/5}. \tag{9} \]

Theorem (b; explicit counterexample). Under the standard uniform meaning of \(\gg\), the posted \(H_2\) assertion is false.

Proof. Suppose the assertion held with an absolute constant \(c>0\). For every prime \(q\), apply it to \(G_q=D(5,q)\). By (6) and the elementary lemma, every qualifying \(H_2\subseteq G_q\) has at most one edge. But (8) would require

\[ e(H_2)\geq c\,\delta_q^2n_q^2=\frac{cq^2}{4}. \]

Choose a prime \(q>2/\sqrt c\), possible because there are arbitrarily large primes. The right side is then greater than \(1\), a contradiction.

\(\square\)

This is the uniformity/finiteness step: the finite \(q=5\) example by itself would not refute an unspecified implicit constant, whereas the same coordinate construction over arbitrarily large prime fields does.

1.4 Exact scope

witness ambiguity: \(G_q\) itself has no cycle of length at most \(8\).

this family, \[ \delta_q^3n_q^2=\frac1{16q^2}\longrightarrow0, \] so it does not refute the \(H_1\) lower bound.

asking whether there exists some fixed \(\beta_0>0\) for all \(0\leq\beta\leq\beta_0\). This family is at \(\beta=4/5\), far outside the ranges \(1/5\) and \(1/3\) discussed below.

qualifier is absent from the verbatim live statement. The conclusion here is therefore about the literal live statement, not a declaration that every historically intended Duke--Erdős--Rödl variant is settled.

2. Standalone from-scratch verification

The verifier is erdos584_wave9t_reverify.py. It uses only the Python standard library.

Run:

python -m py_compile runs/erdos584_wave9t_reverify.py
python runs/erdos584_wave9t_reverify.py

The second command completed in about 10 seconds on this VM. It performs the following independent checks.

  1. Generates every edge from equations (3), rejecting duplicate edges.
  2. Tests every generated edge directly against all four equations (2).
  3. Regenerates each line's neighbourhood independently using the inverse

equations (4) and compares the resulting set with the forward graph.

  1. Scans all \(q^{10}\) point-line pairs for \(q=2,3,5\), evaluating (2)

directly. The \(q=5\) scan covers \(5^{10}=9{,}765{,}625\) pairs.

  1. Checks symmetry, simplicity, bipartiteness, every degree, and exact

vertex and edge counts.

  1. Uses an exhaustive bounded-depth breadth-first search rooted at every

vertex to rule out every cycle of length at most \(8\). Each candidate is reconstructed as a simple cycle and checked edge by edge. The cycle routine first self-tests on a tree and on \(C_3,C_4,\ldots,C_{12}\).

  1. Recomputes (7) and (8) with exact rational arithmetic.

The output was:

q=2: |V|=64, |E|=64, degrees={q}, delta=1/64,
     delta^2*n^2=1, no cycle <=8, no cycle <=10
q=3: |V|=486, |E|=729, degrees={q}, delta=1/324,
     delta^2*n^2=9/4, no cycle <=8, no cycle <=10
q=5: |V|=6250, |E|=15625, degrees={q}, delta=1/2500,
     delta^2*n^2=25/4, no cycle <=8, girth exactly 10
ALL CHECKS PASSED

For \(q=5\), the program also found and validated the following 10-cycle, with coordinates in the notation of (2):

\[ \begin{aligned} &(0,0,0,0,0)_P,\ [3,0,0,0,0]_L,\ (4,3,0,1,0)_P,\ [2,1,4,2,0]_L,\\ &(0,1,4,0,2)_P,\ [1,1,4,1,1]_L,\ (1,0,3,1,3)_P,\ [4,4,2,1,0]_L,\\ &(3,2,0,3,0)_P,\ [1,0,0,0,0]_L, \end{aligned} \]

followed by the first point.

The finite checks are (d). They independently catch transcription, sign, counting, and short-cycle errors in the construction, but they are not substituted for the all-\(q\) girth theorem. The infinite conclusion remains correctly labelled (b) because its uniform step uses LUW Proposition 2.1(iii).

3. Primary-source literature audit

3.1 The sources cited by the live page

  1. Duke--Erdős (1982). The primary scan

Subgraphs in which each pair of edges lies in a short common cycle, Congressus Numerantium 35 (1982), 253--260, exists. Its Corollary 1 says that for each fixed positive density \(c\), sufficiently large \(n\) forces a subgraph with \(c'n^2\) edges in which every edge pair lies on an internal \(C_4\) or \(C_6\), and adjacent edge pairs lie on an internal \(C_4\). This matches the page's fixed-density summary.

  1. Duke--Erdős--Rödl (1984). The primary scan

More results on subgraphs with many short cycles, Congressus Numerantium 43 (1984), 295--300, exists. Its Theorem 3 gives the strong \(C_6\) conclusion at the \(n^{2-5\epsilon}\) scale. The same paper records the weak \(C_6\) \(n^{2-3\epsilon}\) scale and proves an \(n^{2-2\epsilon}\) result with cycles of length at most \(12\).

  1. Fox--Sudakov (2008). The primary preprint

arXiv:0706.1920, later JCTB 98 (2008), 1056--1062, DOI 10.1016/j.jctb.2007.12.003, exists. Its Problem 1.1 explicitly asks for constants \(c,\beta_0>0\) working for \(0\leq\beta\leq\beta_0\), rather than for all densities. Its Theorem 1.2 proves the desired \(n^{2-2\beta}\) \(C_{\leq8}\) scale for \(\beta<1/5\), with the additional conclusion that adjacent selected edges lie together on a cycle of length at most \(6\).

These checks explain the formulation issue precisely: the older sparse problem includes a small-\(\beta\) range quantifier; the live page's literal \(\delta\)-statement does not.

3.2 The 2026 sources in the comments

A note on the formulation of Erdős Problem #584, dated 21 April 2026, exists. Its Theorem 1 invokes the same LUW high-girth family and its Corollary 2 makes the high-girth counterexample. The present result is therefore not claimed as a new discovery. The value added here is an explicit coordinate-level construction, exact counts, a uniformity audit, and a standalone exhaustive checker. The comment's reported issues in that note's unrelated Proposition 4 are immaterial to the proof above, which does not use Proposition 4.

On the Duke--Erdős--Rödl Problem at the One-Third Threshold, arXiv:2606.06522v1, dated 2 June 2026, exists and its Theorems 1.2--1.4 state the results summarized in the live comment. This run checked the identity and theorem statements in the primary preprint but did not independently audit all twenty pages of its proofs. Accordingly, those new results are reported as preprint claims here rather than used in the counterexample.

3.3 Search coverage and honest miss statement

I searched exact titles, the phrases “Duke--Erdős--Rödl” and “cycle-connected subgraphs,” the live problem number, arXiv, and the published DOI. The directly relevant primary mathematical sources found were the 1982 and 1984 papers, Fox--Sudakov 2007/2008, LUW 1995 for the obstruction, and Li's June 2026 preprint. I found no additional primary paper directly advancing this exact problem. This is an indexed-web literature search, not a proof that no unindexed or very recent manuscript exists.

4. Verified state

quantified: the explicit infinite family \(D(5,q)\), \(q\) prime, has no cycle of length at most \(8\), while its requested scale is \(\delta_q^2n_q^2=q^2/4\to\infty\).

counts, densities, and absence of \(C_{\leq8}\) were independently recomputed for \(q=2,3,5\); \(q=5\) included a scan of all \(9{,}765{,}625\) point-line pairs.

not extrapolate from finite computation.

and does not settle the corrected small-\(\beta\) problem.

PROVED: The literal live H2 assertion is false, rigorously modulo LUW Proposition 2.1: explicit D(5,q) graphs have girth at least 10 but require Omega(q^2) H2 edges; the corrected small-beta problem remains open beyond the verified ranges.

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