Erdős problem #560: size Ramsey number of \(K_{n,n}\)

Accessed and checked on 2026-07-27. This report does not solve the asymptotic problem. It gives a fully reproducible exact computation at \(n=2\), classifies the minimum hosts in that case, gives a rigorous concrete bound at \(n=3\), and identifies the quantitative point at which the current lower-bound machinery loses the conjectured factor \(n\).

Claim labels used throughout:

• [A] elementary-rigorous: proved in this report from definitions.
• [B] rigorous modulo named theorem: the exact external theorem and source

are named.

• [C] plausible/structural-unverified: diagnosis or heuristic, not a

theorem.

• [D] computational-only: certified by the supplied exhaustive program,

with the dependency boundary stated explicitly.

1. Mandatory live-page check

I fetched https://www.erdosproblems.com/560 through the Bright Data browser path, not datacenter curl.

Live-page state:

• Status: OPEN.
• Last edited: 18 January 2026.
• Comments: 0.
• Claimed proofs: 0.
• “Interested in collaborating”: None.
• “Currently working on this problem”: None.
• “Likes this problem”, “looks difficult”, “looks tractable”, “results could be

formalisable”, and “working on formalising”: all None.

Thus the stop condition in the task was not triggered.

Verbatim current statement

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 such that in any \(2\)-colouring of the edges of \(H\) there is a monochromatic copy of \(G\).

Determine \[ > \hat{R}(K_{n,n}), > \] where \(K_{n,n}\) is the complete bipartite graph with \(n\) vertices in each component.

The page's current known-results text is:

It says that the lower bound holds for \(n\ge 6\) and is due to Erdős and Rousseau, while the upper bound is due to Erdős--Faudree--Rousseau--Schelp and Nešetřil--Rödl. It also records Conlon--Fox--Wigderson's result

their determination \(\hat R(K_{s,t})\asymp s^2t2^s\) when \(t\gg s\log s\), and their conjecture that the latter estimate holds for every \(s\le t\). In particular, the conjectured diagonal order is

These are treated as the ground-truth asymptotic statements for this run.

2. Literature audit

Verified primary sources

1. [B] P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp,

The size Ramsey number, Periodica Mathematica Hungarica 9 (1978), 145--161. The original paper exists at the stated DOI; an author-archive scan was inspected. Its final open-problems section asks for the complete-bipartite size Ramsey number and records the then-known exponential window.

1. [B] J. Nešetřil and V. Rödl, The structure of critical Ramsey graphs,

Acta Mathematica Academiae Scientiarum Hungaricae 32 (1978), 295--300. The bibliographic record was verified both on Rödl's publication list and Nešetřil's publication list. This is one of the two upper-bound sources cited by the live page.

1. [B] P. Erdős and C. C. Rousseau,

The size Ramsey number of a complete bipartite graph90521-T), Discrete Mathematics 113 (1993), 259--262. The publisher's abstract explicitly says that the paper proves the diagonal lower bound \(\frac1{60}n^2 2^n\).

1. [B] O. Pikhurko,

Asymptotic Size Ramsey Results for Bipartite Graphs, SIAM Journal on Discrete Mathematics 16 (2002), 99--113, DOI. This determines, through a mixed-integer program, the linear asymptotic when the small part \(s\) is fixed and the large part tends to infinity. It does not cover the simultaneous diagonal limit \(s=t\to\infty\).

1. [B] D. Conlon, J. Fox, and Y. Wigderson,

Three early problems on size Ramsey numbers, Combinatorica 43 (2023), 743--768, journal DOI. I inspected arXiv v2. Theorem 1.1 is precisely the \(\Omega(s^{2-s/t}t2^s)\) lower bound; Corollary 1.2 treats \(t=\Omega(s\log s)\); Conjecture 5.1 explicitly predicts \(\Theta(s^2t2^s)\) for all \(s\le t\), including \(\Theta(n^3 2^n)\) on the diagonal.

1. [B] R. J. Faudree and J. Sheehan,

Size Ramsey numbers for small-order graphs, Journal of Graph Theory 7 (1983), 53--55. Its publisher abstract says it tabulates the size or restricted size Ramsey number for every pair of graphs on at most four vertices without isolates, so it covers \(K_{2,2}=C_4\). A later paper, Silaban--Baskoro--Uttunggadewa (2019), explicitly records that the pair \((C_4,C_4)\) attains the complete-graph upper bound. Thus the \(n=2\) exact value below is a verification of a known result, not a novelty claim.

1. [B] H. Harborth and I. Mengersen, *The Ramsey number of

\(K_{3,3}\), in Combinatorics, Graph Theory, and Applications, vol. 2 (Wiley, 1991), 639--644, proved \(r(K_{3,3},K_{3,3})=18\). The bibliographic data and value are recorded in Radziszowski's Small Ramsey Numbers* dynamic survey.

Search miss, stated narrowly

[C] I searched the exact problem/title phrases, arXiv, Crossref/OpenAlex, and forward citations of the Conlon--Fox--Wigderson paper through 2026-07-27. I found no subsequent primary paper improving the diagonal \(\Omega(n^2 2^n)\) lower order or the \(O(n^3 2^n)\) upper order. OpenAlex's forward-citation data are not exhaustive, so this is a reported search miss, not a theorem that no such paper exists. The live page, last edited in January 2026, likewise still marks the problem open.

3. A general finite reduction

Let \(r(G)\) denote the ordinary two-colour Ramsey number of \(G\).

Minimal-host lemma

[A] Proposition. If \(G\) is connected and has minimum degree \(\delta(G)\), every inclusion-minimal graph \(F\) satisfying \(F\to G\) is connected and

Proof. If no component of a disconnected \(F\) arrows \(G\), choose an avoiding colouring independently on every component. Their union avoids a monochromatic connected \(G\), a contradiction. Hence an inclusion-minimal host is connected.

Suppose a vertex \(v\in V(F)\) has \(d_F(v)\le 2\delta(G)-2\). By inclusion-minimality, \(F-v\) has a red/blue colouring with no monochromatic \(G\). Partition the edges incident with \(v\) so that at most \(\delta(G)-1\) are red and at most \(\delta(G)-1\) are blue. No new monochromatic \(G\) can use \(v\), because \(v\) would need at least \(\delta(G)\) incident edges of its colour. This extends the avoiding colouring to \(F\), a contradiction. \(\square\)

Any graph that arrows \(G\) has at least \(r(G)\) vertices: otherwise an avoiding colouring of the complete graph on the same vertex set restricts to an avoiding colouring of the host. The handshake lemma therefore gives:

[A] Corollary.

For \(G=K_{n,n}\), this becomes

This is much weaker than the asymptotic Erdős--Rousseau/CFW bound, but it is useful for exact small cases.

4. Concrete small-\(n\) results

For \(n=3\), insert \(\delta(K_{3,3})=3\) and the Harborth--Mengersen theorem \(r(K_{3,3})=18\) into (1):

The complete host \(K_{18}\) gives

The standalone verifier recomputes both integers.

5. The \(n=2\) case and its host classification

Here \(K_{2,2}=C_4\).

Elementary 15-edge upper bound

[A] Lemma. Every \(C_4\)-free graph on six vertices has at most seven edges.

Proof. Let \(v\) have maximum degree \(d\). If \(d\le2\), there are at most six edges. Suppose \(d\ge3\), put \(A=N(v)\), and let \(B=V\setminus(A\cup\{v\})\), so \(|B|=5-d\).

• The graph induced by \(A\) has maximum degree at most one; two edges in

\(A\) sharing a vertex, together with \(v\), form a \(C_4\). Thus \(e(A)\le\lfloor d/2\rfloor\).

• Every vertex of \(B\) has at most one neighbour in \(A\); two such

neighbours, together with \(v\), form a \(C_4\).

Consequently

For \(d=3,4,5\), the right side is seven. \(\square\)

In every two-colouring of \(E(K_6)\), one colour has at least eight of the 15 edges, so that colour contains a \(C_4\). Therefore \(\hat R(C_4)\le15\).

Exhaustive lower bound and uniqueness

[D] Result. No graph with at most 14 edges arrows \(C_4\). Among graphs with 15 edges, the only arrowing host, apart from adding isolated vertices, is \(K_6\).

The reduction is finite and complete:

1. Choose an inclusion-minimal arrowing subgraph \(F\).
2. By the minimal-host lemma, \(F\) is connected and

\(\delta(F)\ge3\).

1. If \(F\) has \(m\) edges, the handshake lemma gives

\(|V(F)|\le\lfloor2m/3\rfloor\).

1. For every admissible \((|V(F)|,m)\), nauty-geng -c -d3 generates one

representative of every connected simple unlabeled graph.

1. For each generated graph, the checker lists every non-induced \(C_4\) as

a four-edge bit mask. A red mask \(R\) avoids a monochromatic \(C_4\) precisely when, for every cycle mask \(Q\), \(0<|R\cap Q|<4\).

1. Global colour complementation lets the checker fix the first edge red and

inspect \(2^{m-1}\) colourings without loss.

The complete candidate table was:

There were 957 candidates in total. The program produced and rechecked an explicit avoiding colouring for 956. The sole graph without a witness was

(m,n,graph6) = (15,6,E~~w),

and E~~w parses as \(K_6\).

It follows that if a 15-edge graph \(H\) arrows \(C_4\), an inclusion-minimal arrowing subgraph cannot have fewer than 15 edges, so it uses every edge of \(H\). The enumeration then forces its non-isolated part to be \(K_6\). This proves the stated classification conditional only on the exhaustiveness of geng.

Code and independent re-verification

The complete standalone source is runs/erdos560_wave6b_verify.py. Its core colour test is:

def find_avoiding_coloring(graph):
    cycle_masks = c4_edge_masks(graph)
    if not cycle_masks:
        return 0
    m = len(graph.edges)
    # Fix edge 0 red, using global red/blue complementation.
    for red_mask in range(1, 1 << m, 2):
        if all(
            (red_mask & cycle) not in (0, cycle)
            for cycle in cycle_masks
        ):
            return red_mask
    return None

Run:

python runs/erdos560_wave6b_verify.py --sat-cross-check

The default path uses no third-party Python packages: it has its own graph6 parser, \(C_4\) enumerator, and exhaustive edge-colouring loop. The optional cross-check reparses every record with NetworkX and independently solves the two CNF clauses per \(C_4\) with PySAT/MiniSat.

Tested environment:

Python 3.12.3
nauty 2.8.8+ds-5
NetworkX 3.6.1       (optional audit)
PySAT 1.9.dev7       (optional audit)

Exact output:

small-case arithmetic: n=3 reduction gives 45 <= hat R(K3,3) <= 153
direct K6 check: 45 C4s; all 2^14 colorings modulo complement checked
geng executable: /bin/nauty-geng
m= 1: candidates=  0
m= 2: candidates=  0
m= 3: candidates=  0
m= 4: candidates=  0
m= 5: candidates=  0
m= 6: candidates=  1
m= 7: candidates=  0
m= 8: candidates=  1
m= 9: candidates=  3
m=10: candidates=  5
m=11: candidates=  9
m=12: candidates= 27
m=13: candidates= 67
m=14: candidates=198
m=15: candidates=646
total candidates: 957
explicit avoiding witnesses: 956
arrowing records: [(15, 6, 'E~~w')]
candidate sha256: a6aa8f9a7feb020b7d1e1c2ef11cd029fb3d701fd03b71f353aa3af123787386
witness sha256:   4d35895e3f7b0bcd9955b43c2e639354db26d0b84935409dc403b528bf4d19be
independent NetworkX+MiniSat audit: total=957, colorable=956, arrowing=[(15, 6, 'E~~w')]
VERIFIED: hat R(K_{2,2}) = 15; unique 15-edge host is K6 + isolates

The source-file SHA-256 is

2b70a5c83e4a5c72dfb3e58e0457fcdf3b8835c689eed4d7c647f6fdaf500986

Dependency boundary: the colouring claims are checked twice by different algorithms. Completeness of the unlabeled graph list relies on the established nauty/geng generator; no independent graph-isomorph-free generator is included. Accordingly, the new host-classification statement is labelled [D], not elevated to an unaided proof.

6. Exact asymptotic obstruction in the current method

[A, algebra applied to CFW] The Conlon--Fox--Wigderson lower bound gives

At \(s=t=n\), this is exactly of order \(n^2 2^n\). Using monotonicity with \(s=n-2,t=n\), as their proof does to create two units of slack, still gives only

Thus their power improvement off the diagonal degenerates precisely on the diagonal; it cannot supply the missing factor \(n\).

[C] Quantitative wall for this route. In the CFW first-moment calculation, the dangerous term has the schematic form

When \(t-s=O(1)\), their hypergeometric balancing contributes only a polynomial saving raised to \(O(1)\). Raising the proposed edge budget from \(q=\Theta(n^2 2^n)\) to \(q=\Theta(n^3 2^n)\) multiplies the first factor by \(n^n\). Therefore, a CFW-style diagonal proof needs a new balanced-block colouring/counting lemma giving an aggregate \(n^{-n}\) saving, not the \(n^{-O(1)}\) saving produced by constant off-diagonal slack.

This is the exact missing lemma for that method:

Needed CFW-style lemma. For every graph with \(q\le c n^3 2^n\) edges, construct a globally consistent red/blue edge colouring distribution whose total risk over all candidate \(K_{n,n}\)'s gains a factor \(n^{-\Omega(n)}\) over the uniform-colouring count.

No such lemma is proved here. Merely balancing the total red and blue degree at each vertex is insufficient: the obstruction concerns simultaneous containment of the same \(n\)-set in many monochromatic neighbourhoods. On a complete bipartite host one can choose balanced column patterns independently; on an arbitrary host, each edge belongs to two overlapping stars and those local choices must be globally compatible. That consistency/discrepancy problem is the structural point not handled at diagonal strength by the dyadic hypergeometric construction.

7. Why brute force does not naturally extend to \(n=3\)

[A] A minimal \(K_{3,3}\)-Ramsey host has at least 18 vertices, minimum degree at least five, and between 45 and 153 edges under the present bounds. Even its very first possible layer, 18 vertices and 45 edges, consists of 5-regular graphs.

[C, cost estimate only] The standard fixed-degree configuration-model estimate

at \(n=18,d=5\) is about \(3.3\times10^{28}\) labelled graphs, or roughly \(5.1\times10^{12}\) unlabeled graphs after division by \(18!\). The asymptotic estimate is only a scale diagnostic at \(n=18\), not an exact count. Even at an optimistic one millisecond for generation plus SAT checking per graph, that single layer would cost about \(1.4\times10^6\) core-hours, roughly US$70,000 at US$0.05/core-hour, before considering any edge count above

1. I did not run this computation.

The feasible next advance is therefore theoretical: strengthen the minimal-host structure beyond minimum degree, or obtain the \(n^{-\Omega(n)}\) balanced-colouring lemma above. Blind unlabeled enumeration is not a few-CPU-minute path to \(n=3\), much less to the uniform asymptotic problem.

PARTIAL: independently certified \(\hat R(K_{2,2})=15\) and uniquely \(K_6\) as the 15-edge host (up to isolates), proved \(45\le\hat R(K_{3,3})\le153\), but the conjectured diagonal factor \(n\) remains blocked by a missing \(n^{-\Omega(n)}\) balanced-colouring gain.