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.

2. [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.

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

[*The size Ramsey number of a complete bipartite

graph*](https://doi.org/10.1016/0012-365X(93)90521-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\).

4. [B] O. Pikhurko,

[*Asymptotic Size Ramsey Results for Bipartite

Graphs*](https://arxiv.org/abs/math/0101197),

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\).

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

[*Three early problems on size Ramsey

numbers*](https://arxiv.org/abs/2111.05420),

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.

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

[*Size Ramsey numbers for small-order

graphs*](https://doi.org/10.1002/jgt.3190070107),

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)](https://doi.org/10.7151/dmgt.2188), 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.

7. [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

| \(n\) | Verified statement | Status |

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

| 1 | \(\hat R(K_{1,1})=1\) | [A] one edge |

| 2 | \(\hat R(K_{2,2})=15\) | [B] known; independently [D] checked |

| 3 | \(45\le \hat R(K_{3,3})\le153\) | [A]+[B] |

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\).

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

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

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

representative of every connected simple unlabeled graph.

5. 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\).

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

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

The complete candidate table was:

| edges \(m\) | 1--5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |

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

| candidates | 0 | 1 | 0 | 1 | 3 | 5 | 9 | 27 | 67 | 198 | 646 |

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

45. 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.