Erdős problem #558 — wave 6b
Date: 2026-07-27 (UTC)
Claim labels
- (a) elementary-rigorous: a complete proof is given here using only finite counting, modular arithmetic, or elementary linear algebra.
- (b) rigorous-modulo-named-theorem: the claim is quoted from the identified primary source.
- (c) plausible/structural-unverified: an interpretation or novelty assessment, not a theorem.
- (d) computational-only: established by the stated finite computation; it is not promoted to a uniform theorem.
Step 0: authoritative live-page gate
(d: page-observed) I fetched https://www.erdosproblems.com/558 through the Bright Data browser on 2026-07-27. The live page was marked OPEN, last edited 08 February 2026, with 0 comments, 0 claimed proofs, Interested in collaborating: None, and Currently working on this problem: None. Thus the stop condition did not fire.
The live statement, verbatim (line wrapping removed but wording unchanged), is:
> Let 𝑅𝑘(𝐺) denote the minimal 𝑚 such that if the edges of 𝐾𝑚 are 𝑘-coloured then there is a monochromatic copy of 𝐺. Determine 𝑅𝑘(𝐾𝑠,𝑡) where 𝐾𝑠,𝑡 is the complete bipartite graph with 𝑠 vertices in one component and 𝑡 in the other.
The live page lists the following known results.
(b) Chung and Graham prove
\[ (2\pi\sqrt{st})^{1/(s+t)} \left(\frac{s+t}{e^2}\right) k^{(st-1)/(s+t)} \le R_k(K_{s,t}) \le (t-1)(k+k^{1/s})^s, \]and
\[ R_k(K_{2,2})=(1+o(1))k^2. \](b) Alon, Rónyai, and Szabó prove
\[ R_k(K_{3,3})=(1+o(1))k^3 \]and, when \(s\ge (t-1)!+1\),
\[ R_k(K_{s,t})\asymp k^t. \]No prize/tag metadata was used as mathematics.
Literature audit
I kept ordinary Ramsey numbers—colourings of \(K_N\)—separate from “bipartite Ramsey numbers,” whose host is \(K_{N,N}\). Many search hits concern the latter and do not answer this problem.
(b) F. R. K. Chung and R. L. Graham, On multicolor Ramsey numbers for complete bipartite graphs, JCTB 18 (1975), 164–169, DOI 10.1016/0095-8956(75)90043-X90043-X), author PDF, is the primary source for the displayed general bounds.
(b) N. Alon, L. Rónyai, and T. Szabó, Norm-Graphs: Variations and Applications, JCTB 76 (1999), 280–290, DOI 10.1006/jctb.1999.1906, author PDF, states in its abstract and proves that the largest \(N\) admitting a \(k\)-colouring of \(K_N\) without a monochromatic \(K_{3,3}\) is \((1+o(1))k^3\).
(b) For the special case \(K_{2,2}=C_4\), F. Lazebnik and A. Woldar, New Lower Bounds on the Multicolor Ramsey Numbers \(r_k(C_4)\), JCTB 79 (2000), 172–176, DOI 10.1006/jctb.2000.1954, prove \(r_q(C_4)\ge q^2+2\) for odd prime powers \(q\).
(b) A. C. H. Ling, Some applications of combinatorial designs to extremal graph theory, Ars Combinatoria 67 (2003), 221–229, scanned primary PDF, extends that \(C_4\) lower construction to every prime power \(q\) and gives a difference-packing framework for lower bounds on \(r_k(K_{2,t})\).
(b) T.-Y. Li and Q.-Z. Lin, Upper Bounds on the Multicolor Ramsey Numbers \(r_k(C_4)\), Acta Mathematicae Applicatae Sinica 41 (2025), 286–294, DOI 10.1007/s10255-023-1074-3, journal page, prove
\[ r_k(C_4)\le k^2+k-1\qquad\text{for even }k\ge6. \]This postdates and improves the \(C_4\) upper bound summarized on the Erdős Problems page.
(b) As a current secondary cross-check only, Radziszowski’s 2026 Small Ramsey Numbers survey records \(R_4(C_4)=18\), \(27\le R_5(C_4)\le29\), and \(34\le R_6(C_4)\le38\); see DS1.18, p. 62.
(d: search audit) Exact-phrase and notation searches for R_3(K_{2,3}), R(K_{2,3},K_{2,3},K_{2,3}), and the bound 20 found no primary source stating the finite result below. The 2026 small-Ramsey survey also does not list this three-colour case. (c) This is not proof of novelty, so no novelty claim is made; the construction may be folklore or implicit in design-theoretic work.
Main finite result
Theorem
(a)
\[ \boxed{20\le R_3(K_{2,3})\le22.} \]Thus this concrete instance is reduced to the three possibilities \(20,21,22\).
Lower bound: an explicit cyclotomic colouring of \(K_{19}\)
Work in \(\mathbb Z_{19}\). The three nonzero cubic-residue cosets are
\[ \begin{aligned} S_0&=\{1,7,8,11,12,18\},\\ S_1&=\{2,3,5,14,16,17\},\\ S_2&=\{4,6,9,10,13,15\}. \end{aligned} \]They partition \(\mathbb Z_{19}\setminus\{0\}\), and every \(S_i\) is closed under negation.
For distinct \(x,y\in\mathbb Z_{19}\), colour the undirected edge \(\{x,y\}\) by the unique \(c\in\{0,1,2\}\) for which
\[ x-y\pmod {19}\in S_c. \]Negation-closure makes this well-defined for an undirected edge.
Fix a colour \(c\) and vertices \(x\ne y\), and put \(d=y-x\). Their common neighbours in colour \(c\) are counted by
\[ \nu_c(d)=|S_c\cap(d+S_c)|. \]Direct subtraction modulo 19 gives:
| colour \(c\) | differences with \(\nu_c(d)=1\) | differences with \(\nu_c(d)=2\) |
|---:|---|---|
| 0 | \(S_1\) | \(S_0\cup S_2\) |
| 1 | \(S_2\) | \(S_0\cup S_1\) |
| 2 | \(S_0\) | \(S_1\cup S_2\) |
(a) Hence every vertex pair has at most two common neighbours in each colour. A monochromatic \(K_{2,3}\) is exactly a same-colour vertex pair with at least three common neighbours. Therefore this colouring of \(K_{19}\) has no monochromatic \(K_{2,3}\), proving
\[ R_3(K_{2,3})\ge20. \]Each colour graph is 6-regular with 57 edges. The checker independently enumerates all 171 vertex pairs in every colour and obtains the codegree histogram
\[ \{1:57,\ 2:114\} \]for each colour.
Upper bound: wedge count and the equality obstruction
Suppose a 3-colouring of \(K_n\) has no monochromatic \(K_{2,3}\). Write \(d_c(v)\) for the degree of \(v\) in colour \(c\). For any fixed colour \(c\),
\[ \sum_v\binom{d_c(v)}2 =\sum_{\{x,y\}}\operatorname{codeg}_c(x,y) \le 2\binom n2, \]because three common \(c\)-neighbours of a pair would form a \(c\)-coloured \(K_{2,3}\). Summing over the three colours gives
\[ \sum_v\sum_{c=0}^2\binom{d_c(v)}2\le6\binom n2. \tag{1} \]At every vertex,
\[ d_0(v)+d_1(v)+d_2(v)=n-1. \]If \(n-1=3q+r\), \(0\le r<3\), convexity of \(\binom{x}{2}\) gives
\[ \sum_{c=0}^2\binom{d_c(v)}2 \ge r\binom{q+1}{2}+(3-r)\binom q2. \tag{2} \]For \(n=23\), the right side of (2) is
\[ \binom82+2\binom72=70, \]whereas (1), after division by \(n\), allows only
\[ \frac{6\binom{23}{2}}{23}=66. \]So \(K_{23}\) cannot avoid a monochromatic \(K_{2,3}\).
At \(n=22\), both sides are exactly 63. Equality everywhere would therefore be necessary. It forces:
1. \(d_0(v)=d_1(v)=d_2(v)=7\) at every vertex;
2. every distinct vertex pair has exactly two common neighbours in each colour.
Take one colour graph and let \(A\) be its adjacency matrix. Then the preceding two conditions say
\[ A^2=5I+2J. \]The all-ones vector has eigenvalue 7. On its 21-dimensional orthogonal complement, every eigenvalue of \(A\) is \(+\sqrt5\) or \(-\sqrt5\). Since \(A\) has zero diagonal,
\[ 0=\operatorname{tr}(A)=7+r\sqrt5 \]for some integer \(r\), which is impossible: squaring would give \(49=5r^2\). Thus equality at \(n=22\) cannot occur.
(a) Every 3-colouring of \(K_{22}\) therefore contains a monochromatic \(K_{2,3}\), proving
\[ R_3(K_{2,3})\le22. \]Exhausted structured extensions
(d) The explicit \(K_{19}\) colouring has no one-vertex extension. If a new vertex \(\infty\) is joined in colour \(c\) to a set \(A_c\), every pair in \(A_c\) must have at most one common colour-\(c\) neighbour among the old vertices. For each \(c\), exhaustive checking shows that the graph of such allowed pairs has clique number 3. Hence \(|A_c|\le3\) for all three colours, but \(3+3+3<19\).
(d) I exhaustively checked the narrower undirected cyclic ansatz in which the colour of \(\{x,y\}\subset\mathbb Z_n\) depends only on \(\min(|x-y|,n-|x-y|)\). There are:
- exactly 6 valid assignments for \(n=19\), all global colour permutations of
\[ (0,1,1,2,1,2,0,0,2) \]
on distances \(1,\ldots,9\);
- no valid assignment among all \(3^{10}=59049\) possibilities for \(n=20\);
- no valid assignment among all \(3^{10}=59049\) possibilities for \(n=21\).
These negative computations concern only the stated structured families and are not upper bounds for unrestricted colourings.
Exact remaining computation and a symmetry reduction
(a) Since the proven interval is \(20\le R_3(K_{2,3})\le22\), exact determination requires only:
1. decide whether a valid colouring of \(K_{20}\) exists;
2. only if it exists, decide whether one exists on \(K_{21}\).
If \(K_{20}\) is infeasible, the answer is 20. If \(K_{20}\) is feasible but \(K_{21}\) is not, the answer is 21. If \(K_{21}\) is feasible, the answer is 22.
A direct one-hot SAT encoding has variables \(x_{\{i,j\},c}\). It imposes exactly one colour on each edge and, for every disjoint \(A,B\) with \(|A|=2\), \(|B|=3\), the clause
\[ \bigvee_{\substack{a\in A\\b\in B}}\neg x_{\{a,b\},c} \]for each colour \(c\). Before symmetry breaking this gives:
| \(n\) | edge-colour variables | forbidden-\(K_{2,3}\) clauses | total clauses with pairwise one-hot |
|---:|---:|---:|---:|
| 20 | 570 | \(3\binom{20}{2}\binom{18}{3}=465120\) | 465880 |
| 21 | 630 | \(3\binom{21}{2}\binom{19}{3}=610470\) | 611310 |
There is a useful rigorous anchor reduction. Define the local excess at \(v\) above the balanced minimum by
\[ e(v)=\sum_c\binom{d_c(v)}2- \min_{\substack{a+b+c=n-1\\a,b,c\ge0}} \left(\binom a2+\binom b2+\binom c2\right). \]For \(K_{20}\), (1) leaves total excess at most \(1140-20\cdot51=120\), so some vertex has \(e(v)\le6\). After permuting colours and the other vertices, its possible sorted colour-degree triples are only
\[ (7,6,6),(7,7,5),(8,6,5),(8,7,4),(9,5,5),(9,6,4), \]with excesses \(0,1,2,4,5,6\).
For \(K_{21}\), total excess is at most \(1260-21\cdot57=63\), so some anchor has \(e(v)\le3\). Its only possible sorted triples are
\[ (7,7,6),(8,6,6),(8,7,5), \]with excesses \(0,1,2\).
(a) Consequently a certificate-producing exact search needs at most six symmetry-fixed top-level cases for \(K_{20}\), followed, only if necessary, by three for \(K_{21}\).
(d) Exploratory PySAT runs were deliberately capped. A direct unrestricted \(K_{18}\) instance did not finish in 120 seconds even though the \(K_{19}\) construction proves it satisfiable; a sequential-counter encoding of the \((7,6,6)\) anchor case for \(K_{20}\) did not finish in 75 seconds. These timeouts are evidence only that the naive encodings/solver settings are poor, not evidence of infeasibility. No UNSAT claim or SAT nonexistence claim is made.
(c) A realistic next engineering budget is approximately 20–150 core-hours: run the six \(K_{20}\) cases with stronger lex-leader symmetry and CaDiCaL/Kissat portfolio solving, log DRAT/LRAT proofs for every UNSAT case, and independently check any SAT model. On eight cores this is roughly 2.5–19 wall-hours. This is a planning estimate, not a complexity bound; proof logging could increase it substantially.
Structural reduction for the original problem
(a) For every graph \(H\),
\[ R_k(H)>n \quad\Longleftrightarrow\quad E(K_n)\text{ can be partitioned into }k\text{ \(H\)-free graphs}. \]The forward direction takes the colour classes; the reverse direction uses the parts as colours.
(a) Therefore the extremal-number inequality
\[ \binom n2\le k\,\operatorname{ex}(n,H) \]is necessary for an avoiding colouring, but it is not sufficient: it gives room for \(k\) dense \(H\)-free graphs without ensuring that their edge sets can tile \(K_n\).
(c) This identifies the general obstruction in problem #558. Upper bounds can come from \(\operatorname{ex}(n,K_{s,t})\), while matching lower bounds require highly compatible \(K_{s,t}\)-free decompositions. Norm graphs supply that compatibility in the regimes on the live page, but no uniform decomposition theorem matching the extremal threshold is known from the sources checked for general \(s,t\). The exact missing ingredient is either such a decomposition or a genuinely multicolour obstruction stronger than summing the individual extremal bounds.
Reproduction
Run:
python runs/erdos558_wave6b_reverify.py
Expected final line:
VERIFIED: 20 <= R_3(K_{2,3}) <= 22
The standalone checker uses only the Python standard library. Its full source is:
#!/usr/bin/env python3
"""From-scratch verification for the finite progress in Erdős problem #558.
No third-party packages or SAT solvers are used. The script verifies:
1. A 3-colouring of K_19 by cubic-residue cosets modulo 19 has no
monochromatic K_{2,3}, proving R_3(K_{2,3}) >= 20.
2. The arithmetic in the wedge-counting upper bound R_3(K_{2,3}) <= 22,
including the integer obstruction in the equality case n=22.
3. The K_19 witness has no one-vertex extension.
4. Among undirected cyclic colourings, the witness is unique up to the six
colour permutations at n=19, and none exists at n=20 or n=21.
Items 1 and 2 support rigorous arguments written in the accompanying report.
Items 3 and 4 are finite computational claims.
"""
from collections import Counter
from fractions import Fraction
from itertools import combinations, permutations, product
from math import comb
P = 19
K = 3
T = 3
def cubic_cosets_mod_19():
"""Return the three nonzero cubic-residue cosets in F_19."""
cubes = {pow(x, 3, P) for x in range(1, P)}
cosets = [{(multiplier * x) % P for x in cubes} for multiplier in (1, 2, 4)]
expected = [
{1, 7, 8, 11, 12, 18},
{2, 3, 5, 14, 16, 17},
{4, 6, 9, 10, 13, 15},
]
assert cosets == expected
assert set().union(*cosets) == set(range(1, P))
assert sum(map(len, cosets)) == P - 1
assert all(S == {(-x) % P for x in S} for S in cosets)
return cosets
COSETS = cubic_cosets_mod_19()
def color_19(x, y):
"""Colour of the undirected edge {x,y} in the explicit K_19."""
assert x != y
difference = (x - y) % P
hits = [c for c, S in enumerate(COSETS) if difference in S]
assert len(hits) == 1
return hits[0]
def common_neighbors(n, color_function, x, y, c):
return [
z
for z in range(n)
if z not in (x, y)
and color_function(x, z) == c
and color_function(y, z) == c
]
def verify_k19_witness():
edges_by_color = Counter(color_19(x, y) for x, y in combinations(range(P), 2))
assert edges_by_color == Counter({0: 57, 1: 57, 2: 57})
codegree_histograms = []
autocorrelations = []
for c, S in enumerate(COSETS):
autocorrelation = [
len(S.intersection({(d + x) % P for x in S})) for d in range(1, P)
]
assert set(autocorrelation) == {1, 2}
assert max(autocorrelation) == 2
autocorrelations.append(autocorrelation)
histogram = Counter()
for x, y in combinations(range(P), 2):
codegree = len(common_neighbors(P, color_19, x, y, c))
histogram[codegree] += 1
assert codegree <= T - 1
assert histogram == Counter({2: 114, 1: 57})
codegree_histograms.append(dict(sorted(histogram.items())))
# Directly count forbidden shores: a K_{2,3} exists iff some vertex
# pair has at least three common neighbours of one colour.
violations = 0
for c in range(K):
for x, y in combinations(range(P), 2):
common = common_neighbors(P, color_19, x, y, c)
violations += sum(1 for _ in combinations(common, T))
assert violations == 0
return edges_by_color, autocorrelations, codegree_histograms
def balanced_wedge_minimum(total_degree, colors):
"""Minimum of sum_c binom(d_c,2), for nonnegative d_c of fixed sum."""
q, r = divmod(total_degree, colors)
return r * comb(q + 1, 2) + (colors - r) * comb(q, 2)
def verify_upper_bound_arithmetic():
# For a K_{2,3}-free colour class, every pair has at most two common
# neighbours. After summing over three colours and cancelling n, the
# per-vertex balanced lower bound must be at most 3*(2)*(n-1)/2.
data = {}
for n in (22, 23):
lower = balanced_wedge_minimum(n - 1, K)
capacity = Fraction(K * (T - 1) * (n - 1), 2)
data[n] = (lower, capacity)
assert data[23] == (70, Fraction(66, 1))
assert data[23][0] > data[23][1]
assert data[22] == (63, Fraction(63, 1))
# Equality at n=22 would force, in each colour, a 7-regular graph in
# which every distinct pair has exactly two common neighbours. Its
# adjacency matrix would satisfy A^2 = 5I + 2J. Thus its nonprincipal
# eigenvalues are +/-sqrt(5), and trace(A)=0 would require
# 7 + r*sqrt(5)=0 for an integer r in [-21,21]. Squaring would give
# 49 = 5r^2, which has no integer solution.
possible_trace_coefficients = [
r for r in range(-21, 22) if 49 == 5 * r * r
]
assert possible_trace_coefficients == []
# Useful symmetry reductions for any future exact SAT computation.
# Total wedge slack is 120 on K_20 and 63 on K_21, so some anchor
# vertex has local excess at most 6 and 3, respectively.
anchor_patterns = {}
for n, baseline, max_excess in ((20, 51, 6), (21, 57, 3)):
patterns = []
for a in range(n):
for b in range(a + 1):
c = n - 1 - a - b
if 0 <= c <= b:
excess = sum(comb(d, 2) for d in (a, b, c)) - baseline
if excess <= max_excess:
patterns.append(((a, b, c), excess))
anchor_patterns[n] = patterns
assert anchor_patterns[20] == [
((7, 6, 6), 0),
((7, 7, 5), 1),
((8, 6, 5), 2),
((8, 7, 4), 4),
((9, 5, 5), 5),
((9, 6, 4), 6),
]
assert anchor_patterns[21] == [
((7, 7, 6), 0),
((8, 6, 6), 1),
((8, 7, 5), 2),
]
return data, anchor_patterns
def verify_no_one_vertex_extension():
# If a new vertex infinity is joined in colour c to a set A_c, then
# every pair in A_c must have at most one common c-neighbour in K_19.
# Otherwise that pair, infinity, and two old common neighbours form a
# monochromatic K_{2,3}. The graph of allowed pairs has clique number 3.
clique_numbers = []
for c in range(K):
def allowed(x, y):
return len(common_neighbors(P, color_19, x, y, c)) <= 1
has_triangle = any(
all(allowed(x, y) for x, y in combinations(vertices, 2))
for vertices in combinations(range(P), 3)
)
has_four_clique = any(
all(allowed(x, y) for x, y in combinations(vertices, 2))
for vertices in combinations(range(P), 4)
)
assert has_triangle and not has_four_clique
clique_numbers.append(3)
assert sum(clique_numbers) == 9 < P
return clique_numbers
def cyclic_distance_class(a, b, n):
"""Index 0..floor(n/2)-1 of the undirected cyclic distance of a,b."""
assert a != b
d = (a - b) % n
return min(d, n - d) - 1
def valid_cyclic_assignment(n, assignment):
"""Whether a distance-class assignment avoids monochromatic K_{2,3}."""
m = n // 2
assert len(assignment) == m
# Translation and reflection reduce endpoint pairs to {0,d},
# 1 <= d <= floor(n/2).
for c in range(K):
for d in range(1, m + 1):
codegree = 0
for z in range(n):
if z in (0, d):
continue
if (
assignment[cyclic_distance_class(0, z, n)] == c
and assignment[cyclic_distance_class(d, z, n)] == c
):
codegree += 1
if codegree >= T:
return False
return True
def enumerate_cyclic_ansatz():
valid = {}
for n in (19, 20, 21):
m = n // 2
good = [
assignment
for assignment in product(range(K), repeat=m)
if valid_cyclic_assignment(n, assignment)
]
valid[n] = good
expected_19 = (0, 1, 1, 2, 1, 2, 0, 0, 2)
assert len(valid[19]) == 6
assert expected_19 in valid[19]
# The six are exactly the global colour permutations of one witness.
assert {
tuple(permutation[c] for c in expected_19)
for permutation in permutations(range(3))
} == set(valid[19])
assert valid[20] == []
assert valid[21] == []
return {n: len(good) for n, good in valid.items()}, expected_19
def main():
edges, autocorrelations, histograms = verify_k19_witness()
upper_data, anchor_patterns = verify_upper_bound_arithmetic()
extension_cliques = verify_no_one_vertex_extension()
cyclic_counts, cyclic_witness = enumerate_cyclic_ansatz()
print("K19 cubic cosets:", [sorted(S) for S in COSETS])
print("K19 edge counts:", dict(sorted(edges.items())))
print("K19 autocorrelations:")
for c, row in enumerate(autocorrelations):
print(f" color {c}: {row}")
print("K19 codegree histograms:", histograms)
print("one-vertex-extension allowed clique numbers:", extension_cliques)
print("cyclic valid counts (n=19,20,21):", cyclic_counts)
print("cyclic K19 witness by distances 1..9:", cyclic_witness)
print(
"upper arithmetic:",
{n: (lo, int(cap)) for n, (lo, cap) in upper_data.items()},
)
print("future-SAT anchor degree patterns:", anchor_patterns)
print("VERIFIED: 20 <= R_3(K_{2,3}) <= 22")
if __name__ == "__main__":
main()
PARTIAL: An explicit cubic-residue colouring and an elementary spectral count prove \(20\le R_3(K_{2,3})\le22\); unrestricted \(K_{20}\)/\(K_{21}\) feasibility is the exact remaining finite question, while cyclic and one-vertex-extension attempts are exhaustively ruled out.