Erdős problem #714 — wave w011

Date checked: 2026-07-28 (UTC)

Outcome and claim labels

(a) Elementary-rigorous. I prove the following exact finite regime, uniformly for every integer \(r\ge 2\):

The first line is immediate; the last two lines follow from a complement/component argument and three proved subset-sum lemmas. No asymptotic theorem is inferred from these identities.

(d) Computational-only. The standalone checker runs/erdos714_wavew011_reverify.py independently:

1. exhausts the integer partitions used by the proof through \(r=16\);
2. directly checks the two extremal constructions through \(r=8\);
3. exhausts all labelled complements with one fewer than the claimed minimum

number of missing edges for \(r\le 4\), including all \(\binom{36}{5}=376\,992\) candidates for \((r,n)=(4,9)\).

(c) Plausible/structural-unverified. I found no later primary source that resolves the asymptotic problem. This is a report of the searches performed, not a proof that no such source exists.

Claim labels used below have the meanings required in the task:

• (a) elementary-rigorous;
• (b) rigorous modulo the explicitly named theorem or source;
• (c) plausible/structural-unverified;
• (d) computational-only.

Step 0: live-page gate

(b), live-page record. I retrieved both the rendered page and its LaTeX view through the Bright Data browser. The exact statement in the current LaTeX view is pasted verbatim:

Is it true that\[\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?\]

Source: live problem page and live LaTeX view, accessed 2026-07-28.

(b), live-page record. The rendered page says:

• status: OPEN;
• page last edited: 23 January 2026;
• 0 comments on this problem;
• 0 claimed proofs for this problem;
• Interested in collaborating: None;
• Currently working on this problem: None;
• all other displayed interest/difficulty/formalisation markers: None.

Thus neither mandatory stop condition was present.

(b), live-page record. The page lists the following known results and no others:

• Kővári, Sós, and Turán proved

\(\operatorname{ex}(n;K_{r,r})\ll n^{2-1/r}\) for every \(r\ge2\).

• Brown and, independently, Erdős–Rényi–Sós proved the conjectured lower

bound for \(r=3\).

• For \(r=2\),

\(\operatorname{ex}(n;K_{2,2})=(\tfrac12+o(1))n^{3/2}\), since \(K_{2,2}=C_4\).

• It points to problems #147 and #1158 (the latter is the hypergraph

generalisation).

The page cites the original Erdős sources [Er64c], [Er67b], [Er69], [Er71, p.103], [Er74c, p.77], [Er75], [Er81], and [Er93, p.334].

Primary-source literature audit

(b). The cited 1954 paper exists as T. Kővári, V. T. Sós, and P. Turán, “On a problem of K. Zarankiewicz,” Colloquium Mathematicum 3 (1954), 50–57, DOI 10.4064/cm-3-1-50-57. This is the source of the upper-bound method recorded on the live page.

(b). Brown’s paper exists as W. G. Brown, “On graphs that do not contain a Thomsen graph,” Canadian Mathematical Bulletin 9 (1966), 281–285, DOI 10.4153/CMB-1966-036-2. Its opening explicitly defines the Thomsen graph as \(K_{3,3}\), states the conjectured \(c n^{5/3}\) lower bound, and says that the paper proves it. A readable university-hosted copy was checked.

(b). The independent paper exists as P. Erdős, A. Rényi, and V. T. Sós, “On a problem of graph theory,” Studia Scientiarum Mathematicarum Hungarica 1 (1966), 215–235; the Hungarian Academy repository record and scan were checked.

(b). A recent peer-reviewed source still records the first open diagonal case: B. Janzer, O. Janzer, V. Magnan, and A. Methuku, “Tight General Bounds for the Extremal Numbers of 0–1 Matrices,” International Mathematics Research Notices 2024(15), 11455–11463, DOI 10.1093/imrn/rnae129. Its introduction explicitly says that the order of \(\operatorname{ex}(n,K_{4,4})\) is unknown.

(b). Bohman and Keevash, “The early evolution of the \(H\)-free process,” arXiv:0908.0429, DOI 10.1007/s00222-010-0247-x, prove for strictly 2-balanced \(H\) a final-process minimum-degree lower bound

For \(H=K_{r,r}\), their stated application includes \(r\ge5\). Substitution \(v_H=2r\), \(e_H=r^2\) gives, by elementary algebra,

(a), using the live page’s \(r=3\) theorem. Since every \(K_{4,4}\) contains a \(K_{3,3}\), Brown’s \(K_{3,3}\)-free graphs give

Together with Kővári–Sós–Turán this leaves the displayed exponent window

(b). The usual projective norm-graph route does not simply settle this gap. C. Grosu, “A note on projective norm graphs,” arXiv:1607.01141, proves that \(P(q,4)\) contains \(K_{4,6}\) for infinitely many primes \(q\). Therefore those graphs also contain \(K_{4,4}\), even though this norm-graph family has the desired \(n^{7/4}\) edge scale and avoids \(K_{4,7}\).

(c), search audit. I searched combinations of ex(n,K_{r,r}), ex(n,K_{4,4}), balanced Zarankiewicz, K_{4,4}-free, and lower bound, including 2025/2026 queries, on journal pages, arXiv, and institutional repositories. The hits above were relevant; no claimed proof or asymptotic \(K_{4,4}\) improvement was located. Several hits concerned saturation, subdivisions, generalized Turán numbers, crossing numbers, or ordered matrices and therefore did not answer this problem.

Exact finite result

Complement criterion

(a). Let \(G\) be an \(n\)-vertex graph and let \(H=\overline G\). For disjoint \(r\)-sets \(A,B\),

If \(n=2r\), this occurs exactly when the connected components of \(H\) can be divided into two unions of \(r\) vertices. Equivalently, the multiset of component orders of \(H\) has a submultiset summing to \(r\).

(a). If \(n=2r+1\), a \(K_{r,r}\) leaves one vertex \(v\) unused. Consequently \(G\) contains \(K_{r,r}\) exactly when, for some \(v\), the component orders of \(H-v\) have a submultiset summing to \(r\).

Three subset-sum lemmas

Lemma 1 (a). If positive integers \(a_1,\ldots,a_k\) have sum \(2r\) and \(k\ge r+1\), some subcollection has sum \(r\).

Proof (a). Induct on \(r\). The case \(r=1\) is immediate. If all terms are \(1\), choose any \(r\). Otherwise the average is less than \(2\), so there is both a term \(1\) and a (different) term \(a_i\ge2\). Remove that \(1\) and replace \(a_i\) by \(a_i-1\). The new list has sum \(2(r-1)\) and at least \(r\) terms. By induction it has a subcollection of sum \(r-1\). If that subcollection uses \(a_i-1\), restore \(a_i\); otherwise add the removed \(1\). Either operation gives sum \(r\) in the original list. \(\square\)

Lemma 2 (a). If positive integers \(a_1,\ldots,a_k\) have sum \(2r+1\) and \(k\ge r+1\), some subcollection has sum \(r\).

Proof (a). If all terms are \(1\), this is immediate. Otherwise decrease a term \(a_i\ge2\) by \(1\). Lemma 1 gives a subcollection of sum \(r\) in the resulting list. If it omits the decreased term, it is already a solution in the original list. If it includes that term, its original sum is \(r+1\), so its complement in the original list has sum \((2r+1)-(r+1)=r\). \(\square\)

Lemma 3 (a). If exactly \(r\) positive integers have sum \(2r+1\) and no subcollection has sum \(r\), their multiset is

Proof (a). Induct on \(r\), with \(r=1\) immediate. If every term is at least \(2\), the list must be one \(3\) and \(r-1\) copies of \(2\). For even \(r\), \(r/2\) of the \(2\)'s sum to \(r\); for odd \(r\ge3\), the \(3\) and \((r-3)/2\) of the \(2\)'s sum to \(r\). Hence there is a term \(1\).

Remove one \(1\) and decrease some other term \(a_i\ge2\) by \(1\). The new \(r-1\) terms sum to \(2(r-1)+1\). A subcollection of sum \(r-1\) would lift to a subcollection of sum \(r\) exactly as in Lemma 1, so none exists. Induction says the new multiset is \(\{r+1,1^{r-2}\}\). If the decreased term was the \(r+1\), undoing the operation gives \(\{r+2,1^{r-1}\}\). If it was one of the \(1\)'s, undoing gives \(\{r+1,2,1^{r-2}\}\), but the \(2\) together with the \(r-2\) ones has sum \(r\), a contradiction. \(\square\)

The value at \(n=2r\)

Upper bound (a). Suppose \(G\) is \(K_{r,r}\)-free on \(2r\) vertices and set \(H=\overline G\). If \(e(H)\le r-1\), then

The component orders sum to \(2r\), so Lemma 1 supplies a union of components of order \(r\). The complement criterion then supplies a \(K_{r,r}\) in \(G\), a contradiction. Hence \(e(H)\ge r\), or

Construction (a). Let \(H\) be a path on \(r+1\) vertices together with \(r-1\) isolated vertices, and take \(G=\overline H\). The component orders of \(H\) are \(r+1,1,\ldots,1\), so no union has order \(r\). Thus \(G\) is \(K_{r,r}\)-free. Since the path has \(r\) edges,

This proves

The value at \(n=2r+1\)

Construction (a). Let \(H\) be a cycle \(C_{r+2}\) together with \(r-1\) isolated vertices, and put \(G=\overline H\). If an isolated vertex \(v\) is deleted, the component orders of \(H-v\) are \(r+2,1^{r-2}\). If a cycle vertex \(v\) is deleted, they are \(r+1,1^{r-1}\). Neither list has a subcollection summing to \(r\). The complement criterion shows that \(G\) is \(K_{r,r}\)-free, and

Upper bound (a). Again let \(H=\overline G\). First, the component orders of \(H\) cannot themselves have a subcollection of sum \(r\): choose its union as \(A\), choose a vertex \(v\) outside \(A\), and use the other \(r\) outside vertices as \(B\); there is no \(H\)-edge from \(A\) to \(B\), giving a forbidden \(K_{r,r}\) in \(G\).

If \(c(H)\ge r+1\), Lemma 2 would give just such a union. Hence \(c(H)\le r\), and therefore

Assume for contradiction that \(e(H)\le r+1\). Equality holds throughout: \(e(H)=r+1\), \(c(H)=r\), and \(H\) is a forest. Its \(r\) component orders sum to \(2r+1\) and avoid subset sum \(r\), so Lemma 3 says that they are \(r+2,1^{r-1}\).

Let \(T\) be the tree component of order \(r+2\), and delete a non-leaf vertex \(v\) of \(T\). The graph \(T-v\) has at least two components whose orders sum to \(r+1\). Pick one of them, of order \(q\); then \(1\le q\le r\). Together with \(r-q\) of the \(r-1\) isolated components, it is a union of components of \(H-v\) of order \(r\). The complement criterion gives a \(K_{r,r}\) in \(G\), the final contradiction. Thus \(e(H)\ge r+2\), proving

The trivial preceding range

(a). A graph needs at least \(2r\) vertices to contain \(K_{r,r}\). Therefore \(K_n\) is \(K_{r,r}\)-free for \(n\le2r-1\), and

What remains asymptotically

(a). Passing to a maximum cut shows that the original problem is equivalent up to a factor \(2\) to its balanced bipartite version. In incidence language, the required object is an \(n\times n\) zero-one matrix with \(\Omega_r(n^{2-1/r})\) ones and no all-one \(r\times r\) submatrix.

(a). Equivalently, one needs \(n\) neighbourhood blocks on an \(n\)-point ground set, with total size \(\Omega_r(n^{2-1/r})\), such that every \(r\)-set of points lies in at most \(r-1\) blocks. The Kővári–Sós–Turán count

shows that these are exactly the parameters at which the counting capacity becomes tight; the inequality itself supplies no construction.

(a). For \(r=4\), the precise construction lemma still missing is: construct graphs with \(\Omega(n^{7/4})\) edges in which every four vertices have at most three common neighbours. This common-neighbour condition is exactly \(K_{4,4}\)-freeness.

(b). Grosu’s theorem identifies why the off-the-shelf norm graph does not provide that lemma: for infinitely many field sizes it has four vertices with at least six common neighbours.

(c). A finite search over field sizes cannot prove the required uniform construction. A successful algebraic attack would need a uniform fibre bound of \(3\) for all four-tuples (including every degenerate tuple), while retaining \(\Theta(n^{7/4})\) incidences. No such lemma was found in the searched sources.

(d). I did not run a raw search at \(n=10\). There are \(2^{\binom{10}{2}}=2^{45}=35\,184\,372\,088\,832\) labelled graphs; even an unrealistically steady \(10^8\) candidates/second would take about \(98\) core-hours, and a more realistic \(10^7\)/second would take about \(41\) core-days. Symmetry-aware SAT/ILP could be much faster, but that is a separate computation and would still give only another finite case.

Reverification

(d). Command run:

python3 -m py_compile runs/erdos714_wavew011_reverify.py
python3 runs/erdos714_wavew011_reverify.py

(d). Output:

r=4 exponents (target, inherited K33, deletion): (Fraction(7, 4), Fraction(5, 3), Fraction(8, 5))
partition instances checked: 5840
K_r,r copies hit by explicit complements: 151714
exact formula table (r, ex(2r,Krr), ex(2r+1,Krr)):
  (2, 4, 6)
  (3, 12, 16)
  (4, 24, 30)
  (5, 40, 48)
  (6, 60, 70)
  (7, 84, 96)
  (8, 112, 126)
exhaustive lower checks (r, n, min-missing, candidates rejected):
  (2, 4, 2, 6)
  (2, 5, 4, 120)
  (3, 6, 3, 105)
  (3, 7, 5, 5985)
  (4, 8, 4, 3276)
  (4, 9, 6, 376992)
elapsed seconds: 2.140
ALL CHECKS PASSED

(d). SHA-256 of the standalone verifier: 4239c42062dea28cde7f8d2d7d7c522f6edfa2fd1f8441eb90ad80d15607f9df.

Standalone verifier source

#!/usr/bin/env python3
"""Independent checks for the finite-regime result in erdos714_wavew011.md.

Only the Python standard library is used.  The uniform claims in the report are
proved there; this program independently checks the subset-sum lemmas over a
substantial finite range, checks the two constructions directly, and performs
an exhaustive labelled-graph lower-bound search through r=4.
"""

from __future__ import annotations

from fractions import Fraction
from itertools import combinations
from math import comb
from time import perf_counter


def partitions(total: int, minimum: int = 1):
    """Yield all nondecreasing partitions of total into positive integers."""
    if total == 0:
        yield ()
        return
    for first in range(minimum, total + 1):
        for rest in partitions(total - first, first):
            yield (first,) + rest


def has_subset_sum(parts: tuple[int, ...], target: int) -> bool:
    """Exact subset-sum test using a bitset of attainable sums."""
    attainable = 1
    for part in parts:
        attainable |= attainable << part
    return bool((attainable >> target) & 1)


def check_partition_lemmas(max_r: int = 16) -> int:
    """Exhaustively check the three integer-partition lemmas in the report."""
    checked = 0
    for r in range(1, max_r + 1):
        for parts in partitions(2 * r):
            if len(parts) >= r + 1:
                assert has_subset_sum(parts, r), (r, parts, "Lemma 1")
                checked += 1

        for parts in partitions(2 * r + 1):
            if len(parts) >= r + 1:
                assert has_subset_sum(parts, r), (r, parts, "Lemma 2")
                checked += 1
            if len(parts) == r and not has_subset_sum(parts, r):
                expected = (1,) * (r - 1) + (r + 2,)
                assert parts == expected, (r, parts, "Lemma 3")
                checked += 1
    return checked


def edge_index(n: int):
    edges = list(combinations(range(n), 2))
    return edges, {edge: i for i, edge in enumerate(edges)}


def iter_krr_masks(n: int, r: int, index: dict[tuple[int, int], int]):
    """Yield each unoriented K_{r,r} cross-edge set once as an integer mask."""
    vertices = tuple(range(n))
    for left in combinations(vertices, r):
        left_set = set(left)
        remaining = tuple(v for v in vertices if v not in left_set)
        for right in combinations(remaining, r):
            if left >= right:  # identify (left,right) with (right,left)
                continue
            mask = 0
            for u in left:
                for v in right:
                    edge = (u, v) if u < v else (v, u)
                    mask |= 1 << index[edge]
            yield mask


def path_mask(n: int, order: int, index: dict[tuple[int, int], int]) -> int:
    """Edges of a path on vertices 0,...,order-1; other vertices are isolated."""
    assert order <= n
    mask = 0
    for u in range(order - 1):
        mask |= 1 << index[(u, u + 1)]
    return mask


def cycle_mask(n: int, order: int, index: dict[tuple[int, int], int]) -> int:
    """Edges of a cycle on vertices 0,...,order-1; other vertices are isolated."""
    assert 3 <= order <= n
    mask = path_mask(n, order, index)
    mask |= 1 << index[(0, order - 1)]
    return mask


def check_construction(n: int, r: int, missing: int) -> int:
    """Check directly that every K_{r,r} in K_n uses a missing edge."""
    edges, index = edge_index(n)
    assert missing < (1 << len(edges))
    copies = 0
    for cross_edges in iter_krr_masks(n, r, index):
        assert missing & cross_edges, (n, r, "unhit Krr")
        copies += 1
    expected = comb(n, r) * comb(n - r, r) // 2
    assert copies == expected, (n, r, copies, expected)
    return copies


def construction_checks(max_r: int = 8) -> tuple[int, list[tuple[int, int, int]]]:
    """Directly check the report's path/cycle complements."""
    total_copies = 0
    rows = []
    for r in range(2, max_r + 1):
        n0 = 2 * r
        edges0, index0 = edge_index(n0)
        missing0 = path_mask(n0, r + 1, index0)
        assert missing0.bit_count() == r
        total_copies += check_construction(n0, r, missing0)
        assert comb(n0, 2) - missing0.bit_count() == comb(n0, 2) - r

        n1 = 2 * r + 1
        edges1, index1 = edge_index(n1)
        missing1 = cycle_mask(n1, r + 2, index1)
        assert missing1.bit_count() == r + 2
        total_copies += check_construction(n1, r, missing1)
        assert comb(n1, 2) - missing1.bit_count() == comb(n1, 2) - (r + 2)

        rows.append(
            (
                r,
                comb(n0, 2) - r,
                comb(n1, 2) - (r + 2),
            )
        )
    return total_copies, rows


def edge_coverage_masks(n: int, r: int):
    """For each edge, return the bitset of K_{r,r} copies it hits."""
    edges, index = edge_index(n)
    copies = list(iter_krr_masks(n, r, index))
    coverage = [0] * len(edges)
    for copy_number, cross_edges in enumerate(copies):
        remaining = cross_edges
        while remaining:
            low_bit = remaining & -remaining
            edge_number = low_bit.bit_length() - 1
            coverage[edge_number] |= 1 << copy_number
            remaining ^= low_bit
    return edges, copies, coverage


def assert_no_hitting_set(n: int, r: int, missing_edges: int) -> int:
    """Exhaustively reject every complement having exactly missing_edges edges.

    It is enough to check exactly threshold-1 edges: any smaller hitting set
    could be augmented to that size and would remain a hitting set.
    """
    edges, copies, coverage = edge_coverage_masks(n, r)
    all_copies = (1 << len(copies)) - 1
    candidates = 0
    for choice in combinations(range(len(edges)), missing_edges):
        hit = 0
        for edge_number in choice:
            hit |= coverage[edge_number]
        assert hit != all_copies, (n, r, choice, "unexpected hitting set")
        candidates += 1
    assert candidates == comb(len(edges), missing_edges)
    return candidates


def exhaustive_small_lower_bounds():
    """Brute-force the sharp lower bounds for all labelled cases through r=4."""
    cases = [
        # (r, n, claimed minimum number of missing edges)
        (2, 4, 2),
        (2, 5, 4),
        (3, 6, 3),
        (3, 7, 5),
        (4, 8, 4),
        (4, 9, 6),
    ]
    results = []
    for r, n, threshold in cases:
        candidates = assert_no_hitting_set(n, r, threshold - 1)
        results.append((r, n, threshold, candidates))
    return results


def check_exponent_arithmetic():
    """Recompute the exponent comparisons quoted in the literature section."""
    desired_r4 = Fraction(2) - Fraction(1, 4)
    inherited_r3 = Fraction(2) - Fraction(1, 3)
    deletion_r4 = Fraction(2) - Fraction(2, 5)
    assert desired_r4 == Fraction(7, 4)
    assert inherited_r3 == Fraction(5, 3)
    assert deletion_r4 == Fraction(8, 5)
    assert desired_r4 - inherited_r3 == Fraction(1, 12)
    assert inherited_r3 - deletion_r4 == Fraction(1, 15)
    return desired_r4, inherited_r3, deletion_r4


def main() -> None:
    started = perf_counter()

    exponents = check_exponent_arithmetic()
    partition_checks = check_partition_lemmas()
    copy_checks, rows = construction_checks()
    exhaustive = exhaustive_small_lower_bounds()

    print(f"r=4 exponents (target, inherited K33, deletion): {exponents}")
    print(f"partition instances checked: {partition_checks}")
    print(f"K_r,r copies hit by explicit complements: {copy_checks}")
    print("exact formula table (r, ex(2r,Krr), ex(2r+1,Krr)):")
    for row in rows:
        print(" ", row)
    print("exhaustive lower checks (r, n, min-missing, candidates rejected):")
    for row in exhaustive:
        print(" ", row)
    print(f"elapsed seconds: {perf_counter() - started:.3f}")
    print("ALL CHECKS PASSED")


if __name__ == "__main__":
    main()

PARTIAL: Proved exactly that ex(n;K_{r,r}) equals C(n,2) for n<2r, C(2r,2)-r at n=2r, and C(2r+1,2)-(r+2) at n=2r+1, with exhaustive independent checks through r=4; the asymptotic question remains open.