🔢 mathematics

Exact Zarankiewicz Values On Two Finite Frontier Slices

This paper presents a combined, certificate-based computer-assisted proof establishing exact Zarankiewicz numbers for specific finite slices and a neighboring frontier of the Z(m,n,3,3) problem, utilizing orbit certificates, deletion lemmas, and rigorous arithmetic verification to confirm values such as Z(12,n,3,3)=6n for 18≤n≤22 and Z(13,22,3,3)=137.

Original authors: Koyar Afrasyab

Published 2026-08-11

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Koyar Afrasyab

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a city planner trying to build the most efficient road network possible. You have two groups of locations: a set of "Hubs" on one side and a set of "Destinations" on the other. Your goal is to draw as many roads (connections) as you can between them to keep traffic flowing. However, there is a strict zoning law: you are forbidden from building a specific, messy intersection pattern. In math-speak, this forbidden pattern is a "complete bipartite subgraph," or simply, you can't have a situation where three Hubs are all connected to the same three Destinations. If you do, you've broken the rule.

This puzzle is known as the Zarankiewicz problem. It's a classic brain-teaser in the field of combinatorics, which is the branch of mathematics dedicated to counting, arranging, and organizing things. While mathematicians have figured out how to solve this for massive, theoretical cities, the real challenge lies in the "medium-sized" towns. For these specific sizes, the number of possible road maps is so huge that you can't check them all by hand, but they are also too complex for simple formulas to solve. It's a Goldilocks zone of difficulty: too big for a pencil-and-paper proof, but too small for the "asymptotic" shortcuts that work for infinite cities. Solving these exact numbers matters because they reveal the hidden limits of efficiency in networks, from computer chips to social media connections.

Enter Koyar Afrasyab, a researcher who has just cracked open a particularly stubborn set of these medium-sized puzzles. Think of the problem as trying to find the absolute maximum number of roads you can draw on a grid without creating that forbidden "three-by-three" traffic jam. Afrasyab didn't just guess; they built a digital detective agency to hunt down the answer. The paper focuses on two specific "slices" of this problem: grids with 12 rows and grids with 13 rows, paired with various numbers of columns.

The main discovery is a list of exact "speed limits" for these grids. For a grid with 12 rows and anywhere from 18 to 22 columns, the maximum number of roads (edges) you can have without breaking the rule is exactly $6n$ (where $n$ is the number of columns). For example, a 12-by-18 grid can hold exactly 108 roads, and a 12-by-22 grid can hold exactly 132. The paper proves this by showing that if you try to add just one more road to these grids, you inevitably create the forbidden traffic jam.

The most dramatic part of the story involves a 13-by-22 grid. Previous guesses suggested the limit might be as high as 140 roads. Afrasyab's computer-assisted proof acts like a sieve, filtering out every single impossible arrangement. They started by assuming someone could build a grid with 138 roads without breaking the rules. Through a clever process of elimination—checking the "profiles" of how many roads connect to each point—they proved that 138 is impossible. They narrowed it down until they found the true ceiling: 137 roads. They even provided a specific, verified map of 137 roads that works, proving you can reach that number but not go higher.

The paper also fixes the map for several neighboring grids, determining the exact limits for sizes like 13-by-18, 14-by-17, and 15-by-18. For one tricky case, a 16-by-17 grid, the proof confirms you can definitely build 132 roads, but the upper limit is still a tight range between 132 and 133.

What makes this work special is how it was done. The author didn't just run a black-box computer program that said "No solution found." Instead, they created a "certificate-based" proof. Imagine a detective leaving a trail of breadcrumbs: for every impossible scenario they ruled out, they left a mathematical "receipt" (a certificate) that anyone can check with a simple calculator to verify the error. The paper includes a digital package where you can run a single command to replay the entire investigation, checking millions of these receipts to ensure no mistakes were made. It's a rigorous, transparent, and fully reproducible victory for the math community, turning a set of "maybe" answers into a set of "definitely" facts.

Technical Summary: Exact Zarankiewicz Values on Two Finite Frontier Slices

Problem Statement
The paper addresses the Zarankiewicz problem, which seeks the maximum number of edges, denoted $Z(m, n, s, t)$ , in a bipartite graph with parts of size $m$ and $n$ that contains no complete bipartite subgraph $K_{s,t}$ . Specifically, the author focuses on the case $s=t=3$ (avoiding $K_{3,3}$ ) for moderate finite parameters. While asymptotic theory is well-developed, exact values for specific finite dimensions remain difficult due to severe symmetry and the high cost of proof certification. The paper targets a "finite frontier" of previously unresolved or partially resolved values, including the strip $Z(12, n, 3, 3)$ for $18 \le n \le 22$ , the specific case $Z(13, 22, 3, 3)$ , and a cluster of neighboring values around $13 \times 18$ and $16 \times 17$ .

Methodology
The proof is computer-assisted but strictly certificate-based, distinguishing it from methods relying solely on mixed-integer linear programming (MILP) solvers returning "infeasible" or SAT solvers without explicit witnesses. The verification relies on exact integer and rational arithmetic (using Python's Fraction and standard libraries), with floating-point optimization used only for the initial discovery of certificates.

The methodology employs a multi-layered reduction strategy:

Global Relaxation and Degree Profiles: For the $13 \times 22$ case, the author assumes a hypothetical matrix with 138 edges. By analyzing the "penalty" function $p(d) = \binom{d}{3} - 15d + 70$ associated with column degrees, the search space is reduced from all possible matrices to just 83 distinct degree profiles (histograms of column degrees).
Farkas Certificates: For 77 of these 83 profiles, the author constructs exact rational Farkas certificates. These certificates prove infeasibility by demonstrating that the linear constraints imposed by the $K_{3,3}$ -free condition (specifically, that every row triple appears in at most 2 columns) cannot be satisfied by any non-negative integer solution for that profile.
Marked-Row and Leave Enumeration: The remaining six profiles are excluded using more granular techniques. The author fixes a "marked row," deletes it, and analyzes the resulting "leave multigraph" on the remaining 12 points. This involves:
- Congruence Arguments: Using modular arithmetic on row deficits to rule out specific configurations (e.g., profile 6187391).
- Gram Matrix Constraints: Checking rank and determinant conditions of the incidence matrix of residual blocks.
- Exact Enumeration: Exhaustively enumerating residual block designs and applying integer-scaled Farkas certificates to the remaining factorization systems.
Deletion Lemmas and Witnesses: For the $12 \times n$ strip and the frontier closure, the author uses "deletion lemmas" (relating $Z(m, n)$ to $Z(m, n-1)$ ) combined with explicit constructive witnesses (matrices achieving the lower bounds) to establish exact equalities.

Key Contributions and Results
The paper provides a combined, certificate-based proof for the following exact values and bounds:

The $12 \times n$ Strip: Proves $Z(12, n, 3, 3) = 6n$ for $18 \le n \le 22$ . This is established by an exact certificate for $Z(12, 18, 3, 3) = 108$ and subsequent deletion arguments supported by explicit witnesses for $n=19, 20, 21, 22$ .
The $13 \times 22$ Case: Proves $Z(13, 22, 3, 3) = 137$ . The upper bound of 138 is eliminated by the exhaustive profile analysis described above. A lower bound of 137 is confirmed via an explicit construction (a $13 \times 22$ binary matrix with 137 ones and no $K_{3,3}$ ).
Frontier Closure: Establishes exact values for four neighboring cells:
- $Z(13, 18, 3, 3) = 116$
- $Z(14, 17, 3, 3) = 118$
- $Z(14, 18, 3, 3) = 124$
- $Z(15, 17, 3, 3) = 126$
- $Z(15, 18, 3, 3) = 132$
The $16 \times 17$ Interval: Reports the interval $132 \le Z(16, 17, 3, 3) \le 133$ . The lower bound is supported by a new 132-edge witness; the upper bound of 133 is taken from prior literature (Collins et al.). The paper explicitly notes that the exact value for this specific cell is not determined within this work.

Significance and Claims
The author claims this work provides a complete, reproducible, and certificate-based proof for these specific Zarankiewicz values. The significance lies in the rigorous separation of discovery (where floating-point heuristics may be used) from verification (which uses only exact arithmetic).

Reproducibility: The paper includes a "one-command verification gate" that replays all 5.7 million exact non-negativity checks, including the regeneration of degree profiles, the replay of Farkas certificates, and the exhaustive enumeration of residual block designs.
Modesty: The author explicitly states that these results should be regarded as "new computer-assisted proofs pending independent reproduction and peer review." The paper does not claim to solve the general Zarankiewicz problem or provide a universal algorithm, but rather demonstrates a division of labor for finite extremal problems: using coarse global relaxations to eliminate most cases and reserving exact, computationally intensive enumeration for the few "hard" residue profiles.
Prior Art: The author notes that while the $137$-edge construction for $13 \times 22$ was previously reported, the exact upper bound is a new contribution. Similarly, the specific values for the $12 \times n$ strip ( $n=18$ to $21$) and the frontier closure values are reported as new exact results not found in prior indexed literature as of the paper's date (August 2026).

The paper concludes by emphasizing that no unverified DRAT claims, SAT timeouts, or floating-point solver statuses are used as premises for the theorems, ensuring that the mathematical claims rest entirely on explicit finite data and exact arithmetic.

More like this