ERDŐS/DAILY ▸

← back to the ledger

ERDőS #911 · PARTIAL

Erdős problem #911 — wave 6q report

Date of live audit: 2026-07-27 (UTC)

Claim labels

0. Mandatory live-page gate

[d] I loaded the problem page, its LaTeX endpoint, and its discussion page through the installed Bright Data browser path on 2026-07-27. The live page showed:

Thus the mandatory stop condition did not fire.

Here is the live LaTeX statement, copied verbatim:

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges that is Ramsey for $G$.

Is there a function $f$ such that $f(x)/x\to \infty$ as $x\to \infty$ such that, for all large $C$, if $G$ is a graph with $n$ vertices and $e\geq Cn$ edges then\[\hat{R}(G) > f(C) e?\]

[d] The three comments do not contain a result. On 22 October 2025, LouisD first asked whether the reference was wrong, then corrected himself after finding the problem on page 78 as a “last minute addition.” On 23 October 2025, Thomas Bloom replied that he had added the page number for clarity. The live discussion page also warns that comments are unverified.

Live links: problem, LaTeX, discussion.

1. Primary-source audit

[d] Original source. Paul Erdős, “Some of my favourite problems which recently have been solved,” Proceedings of the International Mathematical Conference, Singapore 1981, North-Holland Mathematics Studies 74 (1982), 59–79, DOI 10.1016/S0304-0208(08)70415-870415-8), author-hosted PDF. Printed page 78 starts “I now would like to state two new problems” and describes \(G(n;e)\) with \(e/n\) large. The scanned formula OCRs badly, so I used the live page—not OCR—as the statement. The downloaded PDF SHA-256 was

b4d371de1f8527a73f1e14bcf44fb1f3e6ae5577891b106b77a04c520235f78d.

[d] Foundational definition. P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, “The size Ramsey number,” Periodica Mathematica Hungarica 9 (1978), 145–161, DOI 10.1007/BF02018930, author-hosted PDF. Its PDF defines the size Ramsey number by minimizing host edge count. SHA-256:

7fa421124f7e16da391d97accf77b2a4f4e29a2820ccdc5fe7d35053ff7cfd11.

[d] Fixed-side bipartite asymptotics. Oleg Pikhurko, “Asymptotic Size Ramsey Results for Bipartite Graphs,” SIAM Journal on Discrete Mathematics 16 (2002/03), 99–113, DOI 10.1137/S0895480101384086, arXiv:math/0101197v2. It computes asymptotics for uniform blow-ups with a fixed template, including \(K_{s,n}\) for fixed \(s\). Near the end of its introduction it explicitly says its method does not work when both vertex classes of the forbidden graphs grow. SHA-256 of the v2 PDF:

06e12026a45564e0a972a1013183dbcf71e03edc11786534d866fa0fb9aaae06.

[b] Strongest directly useful modern result located. David Conlon, Jacob Fox, and Yuval Wigderson, “Three early problems on size Ramsey numbers,” Combinatorica 43 (2023), 743–768, DOI 10.1007/s00493-023-00034-7, arXiv:2111.05420v2. Their Theorem 1.1 states, for all \(s\leq t\),

\[ \widehat r(K_{s,t})=\Omega\!\left(s^{\,2-s/t}t2^s\right), \]

and Corollary 1.2 gives

\[ \widehat r(K_{s,t})=\Theta(s^2t2^s) \quad\text{when }t=\Omega(s\log s). \]

The v2 PDF SHA-256 was

8030838683a72e006d040595e5b20b115689935645b527fe58c0beed7de19021.

[d] Search outcome, not a nonexistence theorem. Searches using the exact wording, Erdős #911, size-Ramsey plus average/minimum degree, dense targets, and citations forward/backward from the papers above found no primary paper explicitly claiming this problem or its uniform statement. This is only an honest search report; it does not prove that no such paper exists. The live page itself gives the same caveat.

2. Elementary facts used

Write \(H\to F\) when every red/blue edge-colouring of \(H\) contains a monochromatic copy of \(F\).

[a] Target monotonicity. If \(F\subseteq G\), then

\(\widehat R(G)\geq\widehat R(F)\). Indeed, every host that arrows \(G\) also arrows \(F\).

[a] Universal two-pile bound. If \(F\) has \(m\) edges, then

\[ \widehat R(F)\geq 2m-1. \]

For a host with at most \(2m-2\) edges, partition its edges into two piles of at most \(m-1\) edges and use the piles as the two colours. Neither colour can contain \(F\).

3. Exact reduction to one uniform minimum-degree statement

For an integer \(d\geq1\), define

\[ \beta(d):= \inf\left\{ \frac{\widehat R(F)}{e(F)}: F\text{ is a finite simple bipartite graph and }\delta(F)\geq d \right\}. \tag{1} \]

The class is nonempty because it contains \(K_{d,d}\), and every finite target has finite size Ramsey number by finite Ramsey’s theorem. Also \(\beta(d)\) is nondecreasing.

Reduction theorem

[a] The live statement of Erdős #911 has an affirmative answer if and only if

\[ \boxed{\displaystyle \frac{\beta(d)}d\longrightarrow\infty.} \tag{2} \]

This is an exact asymptotic equivalence; only fixed explicit constants are lost.

Forward implication

Assume the requested \(f\) exists. Let \(F\) be bipartite with

\(\delta(F)\geq d\), \(v=v(F)\), and \(m=e(F)\). The handshake lemma gives

\[ m\geq \frac{dv}{2}. \]

For all sufficiently large \(d\), apply #911 with \(C=d/2\):

\[ \frac{\widehat R(F)}m>f(d/2). \]

This holds for every \(F\) in (1), so

\[ \beta(d)\geq f(d/2) \quad\Longrightarrow\quad \frac{\beta(d)}d \geq \frac12\,\frac{f(d/2)}{d/2} \longrightarrow\infty. \]
Reverse implication

Assume (2). Let \(G\) have \(n\) vertices and \(e\geq Cn\) edges.

1. A uniformly random bipartition retains each edge with probability \(1/2\), so some cut gives a spanning bipartite subgraph \(B\subseteq G\) with

\(e(B)\geq e/2\).

2. Starting from \(B\), repeatedly delete a vertex whose current degree is

\(

\(Cn/4\leq e/4\) edges are removed in total.

3. The remaining graph \(F\) is nonempty, bipartite, and satisfies

\[ e(F)>e/4,\qquad \delta(F)\geq \left\lceil C/4\right\rceil. \tag{3} \]

Put \(d=\lceil C/4\rceil\). Target monotonicity, (1), and (3) give

\[ \widehat R(G) \geq \widehat R(F) \geq \beta(d)e(F) > \frac{\beta(\lceil C/4\rceil)}4\,e. \]

Consequently one may take

\[ f(C)=\frac14\,\beta(\lceil C/4\rceil). \tag{4} \]

Since \(\lceil C/4\rceil/C\to1/4\), assumption (2) makes

\(f(C)/C\to\infty\), exactly as required.

[a] Baseline and size of the gap. A bipartite graph of minimum degree

\(d\) has at least \(d\) vertices in each part and at least \(d^2\) edges.

The two-pile bound therefore gives only

\[ \beta(d)\geq 2-\frac1{d^2}, \]

whereas (2) asks for \(\beta(d)=\omega(d)\). The missing factor is not a rounding or average-to-minimum-degree issue; it is the entire Ramsey-colouring step for arbitrary bipartite minimum-degree targets.

4. A regime covered by the complete-bipartite theorem

[b] Suppose \(G\) contains \(K_{s,t}\), where \(s\leq t\), and that this biclique accounts for a fixed fraction of the target’s edges:

\[ st\geq \eta e(G),\qquad \eta>0. \]

Target monotonicity and Conlon–Fox–Wigderson Theorem 1.1 imply

\[ \frac{\widehat R(G)}{e(G)} \geq \Omega\!\left(\eta\,s^{\,1-s/t}2^s\right). \tag{5} \]

In particular, if \(\eta\) is bounded below and \(s\geq aC\) for a fixed

\(a>0\), then (5) is exponentially larger than \(C\). Thus #911 holds, with room to spare, on this concrete “edge-dominating linear biclique” subclass.

This is genuinely nonuniform in the target structure: density alone does not force even a \(K_{2,2}\), as the next family demonstrates.

5. Explicit obstruction to a biclique-extraction proof

For each prime \(q\), let \(P_q\) be the incidence graph of the projective plane

\(\mathrm{PG}(2,q)\). Points are one-dimensional subspaces represented by normalized nonzero triples in \(\mathbb F_q^3\); lines are normalized nonzero coefficient triples; a point \(x\) is adjacent to a line \(a\) when \(a\cdot x=0\).

[a] There are \(N=q^2+q+1\) vertices in each part. Every point and line has degree \(d=q+1\), so

\[ n(P_q)=2N,\qquad e(P_q)=dN,\qquad \frac{e(P_q)}{n(P_q)}=\frac{q+1}{2}. \tag{6} \]

Two distinct points lie on exactly one common line: their representing vectors span a two-dimensional subspace, whose orthogonal complement is one-dimensional. Therefore \(P_q\) is \(C_4\)-free. Since every \(K_{s,t}\) with \(s,t\geq2\) contains a \(K_{2,2}=C_4\), \(P_q\) contains no such biclique.

[d] The standalone checker constructs these graphs directly over the prime fields and verifies all degrees, edge counts, and pairwise common-neighbour counts:

| \(q\) | \(d=q+1\) | \(N\) per part | \(n=2N\) | \(e=dN\) | \(e/n\) |

|---:|---:|---:|---:|---:|---:|

| 2 | 3 | 7 | 14 | 21 | \(3/2\) |

| 3 | 4 | 13 | 26 | 52 | \(2\) |

| 5 | 6 | 31 | 62 | 186 | \(3\) |

| 7 | 8 | 57 | 114 | 456 | \(4\) |

| 11 | 12 | 133 | 266 | 1596 | \(6\) |

[a] Primes are unbounded, so (6) is an infinite family in the

\(C\to\infty\) regime. An affirmative answer to #911 would in particular imply

\[ \widehat R(P_q)=\omega(q)\,e(P_q)=\omega(q^4). \tag{7} \]

[c] I regard \(P_q\), and more generally high-girth regular bipartite graphs, as a sharp stress test for prospective proofs: they have the minimum-degree structure isolated by (2) while defeating every argument whose only Ramsey input is extraction of a nontrivial complete bipartite target. This does not assert an upper or lower estimate for \(\widehat R(P_q)\) beyond the elementary bounds above.

6. Exactly what remains

The uniform missing lemma is now precise:

> Prove that every finite simple bipartite \(F\) with

> \(\delta(F)\geq d\) satisfies

> \(\widehat R(F)\geq g(d)e(F)\) for one universal

> \(g(d)=\omega(d)\).

[a] This lemma is neither merely sufficient nor merely a convenient special case: by the reduction theorem, it is equivalent to #911 up to the explicit transformations \(C=d/2\) and \(d=\lceil C/4\rceil\).

[b] The known \(K_{s,t}\) theorem supplies this growth when a sufficiently large biclique carries enough of \(e(F)\), but it does not cover \(C_4\)-free minimum-degree-\(d\) graphs. Pikhurko’s fixed-template linear-programming theory likewise does not provide the needed uniformity when both dimensions/degree scales grow.

[c] The next meaningful attack therefore needs a colouring lemma that uses global minimum degree without codegree concentration—equivalently, one that remains strong on the incidence graphs \(P_q\). A finite search over a few targets cannot establish (2), because both the target and the degree parameter range without bound.

This report does not claim #911 is solved. Its verified mathematical output is the equivalence (2), the positive biclique-dominating regime (5), and the explicit infinite obstruction family (6).

7. Reproduction and independent checks

The standalone verifier is

erdos911_wave6q_verify.py. It uses only the Python standard library plus the system pdftotext; live rechecking additionally uses the installed Bright Data helper.

Commands:

python3 runs/erdos911_wave6q_verify.py
python3 runs/erdos911_wave6q_verify.py --sources
python3 runs/erdos911_wave6q_verify.py --live
python3 runs/erdos911_wave6q_verify.py --all

The offline check does the following from scratch:

for every nonempty labelled simple graph G on 2,...,6 vertices:
    enumerate every cut and retain a maximum cut B
    assert 2*e(B) >= e(G)
    repeatedly delete current-degree < e(G)/(4*v(G))
    assert the resulting bipartite core has > e(G)/4 edges
    assert every remaining degree is >= e(G)/(4*v(G))

for q in 2,3,5,7,11:
    enumerate normalized nonzero triples modulo q
    join point x to line a exactly when dot(a,x) == 0 mod q
    check N=q^2+q+1, degree q+1, and all edge totals
    check every same-side vertex pair has exactly one common neighbour

[d] The exhaustive graph portion covers all

\[ (2^1-1)+(2^3-1)+(2^6-1)+(2^{10}-1)+(2^{15}-1) =33{,}861 \]

nonempty labelled graphs of orders \(2\) through \(6\). It is a finite independent check of the extraction mechanics, not a replacement for the general proof in Section 3.

[d] --sources downloads and hash-pins all four primary PDFs above and checks their relevant textual theorem markers. --live independently repeats the OPEN/no-proof/no-worker gate, statement markers, and all three comment markers through Bright Data. On 2026-07-27, the offline, source, and live runs all ended with ALL REQUESTED CHECKS PASSED.

PARTIAL: Erdős #911 is exactly reduced, up to explicit constants, to proving \(\beta(d)=\omega(d)\) for bipartite minimum-degree-\(d\) targets; projective-plane incidence graphs certify that biclique extraction alone cannot cover the remaining regime.

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