Erdős problem 181 — wave 5l report

Access date: 2026-07-26 (UTC)

Claim labels

• [A] elementary-rigorous: proved directly here without an external theorem.
• [B] rigorous-modulo-named-theorem: follows from the cited published theorem.
• [C] plausible/structural-unverified: an interpretation, extrapolation, or literature-search conclusion, not a theorem.
• [D] computational-only: established by the exact program run described below, with its stated software trust boundary.

The finite result below is a reproducible independent verification of a known theorem, not a claim to have solved the asymptotic problem.

0. Mandatory live-page check

I accessed the Cloudflare-protected page through the Bright Data browser path:

• live problem page
• live discussion thread
• live LaTeX rendering

The browser extraction and full-page screenshot agreed on all of the following:

• Status: OPEN.
• Claimed proofs: 0.
• “Currently working on this problem”: None.
• “Interested in collaborating”: None.
• There is one comment, posted by onetwothreefour at 19:01 on 23 July 2026. It only reports the typo “althouhg,” includes an AI-disclosure note, and makes no mathematical claim.

Thus none of the mandatory stop conditions applied.

Verbatim live statement

> Let \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Prove that

> \[ > R(Q_n) \ll 2^n. > \]

Here \(R(Q_n)=R(Q_n,Q_n)\), and the implied constant in \(\ll\) must be absolute.

Results listed on the live page

The page attributes the conjecture to Burr and Erdős. It also says that Erdős and Sós had not even decided whether \(R(Q_n)/2^n\to\infty\). The page gives the trivial comparison

for some \(C>1\), and lists Tikhomirov’s bound

as the current best, with \(c\approx0.03656\) permissible. These are observations from the authoritative page, not new claims in this report.

1. Primary-source literature audit

Verified sources

1. [B] Konstantin Tikhomirov, A remark on the Ramsey number of the hypercube, arXiv:2208.14568v3 (2 March 2024), published in European Journal of Combinatorics 120 (2024), article 103954, DOI 10.1016/j.ejc.2024.103954. I downloaded and searched the author manuscript. Its Theorem 1.1 proves that every bipartite graph of density at least \(1/2\), with at least \(2^{2n-cn}\) vertices in each part, contains \(Q_n\), for all sufficiently large \(n\). Corollary 1.2 gives

\[ R(Q_n)\le 2^{2n-cn+1}+2. \]

The proof permits \(c=0.03656\). In the parameter calculation, the relevant limiting root is

\[ \frac{-25+\sqrt{881}}{128}=0.03657534499462234\ldots. \]

2. [B] Bernard Lidický and Florian Pfender, Semidefinite Programming and Ramsey Numbers, arXiv:1704.03592v2, published in SIAM Journal on Discrete Mathematics 35(4) (2021), 2328–2344, DOI 10.1137/18M1169473. Their Theorem 3 states

\[ R(Q_3,Q_3)=13. \]

They say the exact result came from complete enumeration and report 8,063 Ramsey graphs. The paper’s flag-algebra computation alone gave only an upper bound of 14. I also downloaded its arXiv ancillary source and verified that the RQ3Q3 instance and cube data actually exist.

3. [B] The Burr–Erdős bibliographic item is real: S. A. Burr and P. Erdős, On the magnitude of generalized Ramsey numbers for graphs, in Infinite and Finite Sets, Colloq. Math. Soc. János Bolyai 10 (1975), 215–240, MR0371701. Tikhomirov’s primary-source reference list identifies this as the source of the conjecture.

4. The cited Erdős paper is bibliographically verified as P. Erdős, Some of my favorite solved and unsolved problems in graph theory, Quaestiones Mathematicae 16(3) (1993), 333–350, DOI 10.1080/16073606.1993.9631741. I did not obtain an independently searchable copy of page 346, so the specific Erdős–Sós attribution is taken from the live page rather than presented as a separately checked quotation.

Search scope and misses

I searched exact-title, exact-bound, and hypercube-Ramsey queries over arXiv and publisher pages, including recent 2024–2026 results. I excluded papers on poset Ramsey numbers inside a hypercube, Ramsey properties of edges of a host hypercube, and oriented hypercubes, because those use different Ramsey notions. A bulk arXiv API attempt was rate-limited (HTTP 429) and then timed out; targeted arXiv and publisher searches worked.

[C] I found no post-Tikhomirov primary source improving the exponent \(2-c\). This is an honest search result, not a proof that no such paper exists. It agrees with the live page’s current-best statement as of the access date.

2. Concrete verified output: the exact table through \(Q_3\)

| Dimension | Graph | Exact diagonal Ramsey number | Status |

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

| 1 | \(Q_1=K_2\) | \(2\) | [A] immediate |

| 2 | \(Q_2=C_4\) | \(6\) | [D] independently exhausted here; also elementary-classical |

| 3 | 3-cube | \(13\) | [B] Lidický–Pfender; [D] independently reverified here |

The standalone verifier is:

Its SHA-256 in this run was:

82f78e1ace608dde5aaee9dbfb73f16c8c83e38bb3a4f9fc745115151a5537c6

The verifier uses only the Python standard library, a C compiler, make, and a pinned nauty 2.8.8 source archive. It accepts --nauty-src PATH for an offline source tree.

3. Explicit 12-vertex construction

[D] On vertices \(0,\ldots,11\), color the following 32 edges red and every other edge blue:

0:  1 2 3 6 7 9
1:  5 6 8 9
2:  3 5 7 8
3:  5 7 8
4:  6 7 10 11
5:  6 7 9
6:  9 11
7:  10
8:  9 10 11
9:  10
10: 11

Each row lists only higher-numbered neighbors. The blue complement has 34 edges.

The independent Python checker generates all 840 labeled edge sets of \(Q_3\) on a fixed 8-set, then checks all

possible red embeddings and the same number of blue embeddings. It finds none. Therefore this coloring proves \(R(Q_3)\ge13\), subject only to the finite computation trust stated below.

For \(Q_2=C_4\), the script checks the red 5-cycle/blue 5-cycle coloring of \(K_5\), then exhausts all \(2^{15}=32{,}768\) colorings of \(K_6\); every \(K_6\) coloring has a monochromatic \(C_4\).

4. Exact upper verification for \(R(Q_3)\)

4.1 The local detector

[A] A graph contains \(Q_3\) if and only if it has eight distinct vertices

containing the twelve edges

Map these vertices to \(000,100,010,001,110,101,011,111\), respectively. Extra host-graph edges are irrelevant because the Ramsey copy need not be induced.

The C detector uses exactly this characterization in each color. Since nauty geng constructs a graph one vertex at a time and cube-freeness is hereditary, a newly appearing cube must contain the newest vertex. Since \(Q_3\) is vertex-transitive, that vertex may be used as \(r\).

4.2 Independent detector cross-check

[D] Plain nauty generates 12,346 unlabeled graphs on 8 vertices. An independent Python checker, using the literal list of 840 cube edge sets rather than the rooted C algorithm, finds that exactly 10,573 of them have neither a red \(Q_3\) nor a blue \(Q_3\). The C pruning plugin independently returns the same 10,573 count.

This order-8 comparison tests every possible adjacency pattern on the eight selected vertices, including every pattern of extra edges. Thus it is a direct finite cross-check of the local C predicate used at larger orders.

4.3 Isomorph-free counts

[D] The exact order-12 generation gave:

| Red-edge range | Unlabeled feasible graphs |

|---|---:|

| \(0\le e(G)\le32\) | 6,153 |

| \(e(G)=33\) | 3,820 |

There are 66 edges in \(K_{12}\). Complementation pairs the \(e<33\) classes with the \(e>33\) classes. Canonical labeling of every balanced class and its complement found no self-complementary feasible class, and paired the 3,820 balanced classes into 1,910 color-swap orbits. Hence:

unlabeled red-graph representations, and

orbits after also identifying a global red/blue swap. This independently reproduces the exact number reported by Lidický and Pfender.

There are 78 edges in \(K_{13}\). In any coloring, either red has at most 39 edges or swapping the colors produces such a representative. The isomorph-free search over the complete range \(0\le e(\mathrm{red})\le39\) returned:

0 feasible colorings

Thus every red/blue coloring of \(K_{13}\) contains a monochromatic \(Q_3\). Together with the explicit \(K_{12}\) coloring, this gives \(R(Q_3)=13\).

4.4 Reproduction transcript

Command run:

python runs/erdos181_wave5l_reverify.py --nauty-src /tmp/nautysrc

Output:

Q2: checked K5 lower construction and all 32768 K6 colourings; R(Q2)=6
Q3 lower: explicit K12 colouring has 32 red and 34 blue edges; neither colour contains Q3
detector cross-check: all 12346 unlabeled order-8 graphs -> 10573 feasible (Python = C plugin; 0.02s plugin run)
order 12: 6153 classes with <=32 red edges; 3820 balanced; 16126 unlabeled colourings = 8063 colour-swap orbits (20.35s generation)
order 13: exhaustive isomorph-free search with 0..39 red edges found 0 feasible colourings (19.49s)
VERIFIED TABLE: R(Q1)=2, R(Q2)=6, R(Q3)=13
ALL CHECKS PASSED in 61.28s

Running without --nauty-src downloads the official nauty 2.8.8 archive and checks the pinned SHA-256

159d2156810a6bb240410cd61eb641add85088d9f15c888cdaa37b8681f929ce

before compiling it in a temporary directory.

4.5 Computational trust boundary

The lower construction is checked by a separately written literal embedding enumerator. The upper check depends on the correctness of Python, the C compiler, nauty 2.8.8’s canonical augmentation, and the small C predicate. The all-graphs order-8 comparison and the independently published 8,063 count are strong cross-checks, but this is not a formally verified proof certificate. Accordingly, all new finite-computation claims are labeled [D], not [A].

5. Failed direct SAT route and measured cost

I also generated the direct edge-variable CNF. A Boolean variable records each edge color. For every embedded cube, one clause forbids all-red edges and one forbids all-blue edges.

• \(K_{12}\): 66 variables, 415,800 embedded cubes, 831,600 clauses. Kissat found a model in 5.56 seconds; that model is the explicit construction above.
• \(K_{13}\): 78 variables, 1,081,080 embedded cubes, 2,162,160 clauses. Building took 7.4 seconds and about 204 MiB, but the unsatisfiable solve had not finished after 180 seconds and was terminated.

This timeout is not evidence of satisfiability or unsatisfiability. It motivated the isomorph-free hereditary enumeration, which completed the decisive order-13 check in about 19 seconds.

6. Elementary general lower bound

[A] For every \(n\ge1\),

Indeed, take disjoint vertex sets \(A,B\) of sizes \(2^n-1\) and \(2^{n-1}-1\). Color edges inside each part red and edges between the parts blue. Each red component has fewer than \(2^n\) vertices. The blue graph is complete bipartite, but the connected bipartite graph \(Q_n\) has two uniquely determined bipartition classes of size \(2^{n-1}\), while \(B\) is smaller. Thus this coloring of \(3\cdot2^{n-1}-2\) vertices has no monochromatic \(Q_n\).

This has the right \(2^n\) scale but, of course, gives no upper bound.

7. Clean asymptotic reduction and the exact wall

Define \(D(n)\) to be the least integer \(M\) such that every bipartite graph with two parts of size \(M\) and at least \(M^2/2\) edges contains \(Q_n\).

[A] Majority-cut reduction.

Given a red/blue coloring of \(K_{2D(n)}\), split its vertices into two equal parts. At least half of the cross-edges have one color, so that color’s cross-edge graph contains \(Q_n\) by the definition of \(D(n)\).

Consequently, the following concrete density-embedding lemma would close Erdős 181:

[A] This lemma is sufficient; I do not claim it is logically necessary, since a Ramsey-specific proof could avoid the majority-cut route.

[B] Tikhomirov proves

for all sufficiently large \(n\), with \(c=0.03656\) permissible. Thus the remaining exponent gap in this clean density formulation is from approximately \(1.96344\) down to \(1\).

[B] The earlier general dependent-random-choice theorem of Conlon–Fox–Sudakov says that a bipartite graph \(H\) on \(m\) vertices and maximum degree \(d\) has

Substituting \(H=Q_n\), \(m=2^n\), and \(d=n\) gives only \(2^{2n+6}\). Tikhomirov also cites bipartite degree-\(d\) graphs whose Ramsey numbers are \(2^{\Omega(d)}m\). Therefore no theorem using only \((m,d)\) can yield an absolute multiple of \(2^n\) for cubes; a cube-specific structural input is mandatory.

[B] Tikhomirov identifies why the naïve random dependent-random-choice embedding stalls: dense block-structured bipartite graphs can make most \(n\)-fold common neighborhoods concentrate in a small set. His appendix proves failure of that randomized embedding procedure, not that those host graphs are \(Q_n\)-free. His successful proof adds facet-wise block embeddings and a trichotomy among non-condensed neighborhoods, density increment, and block structure.

[C] Precise diagnosis. The missing uniform step is a cube-specific embedding theorem at linear host-part size, such as \(D(n)=O(2^n)\), which simultaneously handles all three structural regimes without an exponential loss in \(n\). The inequality producing \(c\approx0.036575\) in the current trichotomy is far from allowing \(c=1\); this is not a matter of rounding the existing constants. The exact computations for \(n\le3\) provide no uniform mechanism in \(n\), so they do not close any part of this asymptotic gap.

8. Why extending the exact computation is not the asymptotic route

[A] The number of labeled \(Q_4\) edge sets on a fixed 16-set is

Thus even at host order 16, the literal two-color CNF would have 108,972,864,000 cube-forbidding clauses, each of length 32.

[C] Cost estimate. At the measured Q3 clause-generation rate of about \(2.92\times10^5\) clauses/second, merely emitting that \(K_{16}\) formula would take about 104 core-hours and at least 13.9 TB for raw 32-bit literals, before SAT solving and container overhead. Any relevant larger host order grows by the factor \(\binom N{16}\). A tailored symmetry-aware program might do much better, as it did for \(Q_3\), but the naïve exact route is already outside the allowed computation and offers no plausible uniform asymptotic argument.

Outcome

The asymptotic conjecture remains open. The concrete deliverable is a fully reproducible exact finite table through dimension 3, an explicit 12-vertex extremal coloring, an independent reproduction of all 8,063 color-swap orbits, and a clean statement of the density-embedding lemma still missing from the majority-cut approach.

PARTIAL: Independently verified R(Q1)=2, R(Q2)=6, and R(Q3)=13 (explicit K12 witness, 8,063 orbit reproduction, exhaustive zero at K13); Erdős 181 remains open, with D(n)=O(2^n) the precise sufficient density-embedding lemma still missing.