House of Graphs Contributions
Why these. These are extremal-graph witnesses. A saturation number or a Zarankiewicz number is an existence claim, and the honest form of the claim is a concrete graph you can hold. Each witness here was computed by SAT solving or exhaustive enumeration, re-verified from scratch against its own graph6 string, and deposited to the House of Graphs so anyone can retrieve it, decode it, and check the property themselves. The values sit in the same computational program as my OEIS work: three of the Zarankiewicz witnesses realize terms of classical OEIS sequences.
Deposited witnesses
These four graphs are live on the House of Graphs with confirmed ids.
| Result | Witness | House of Graphs |
|---|---|---|
| sat(8, C6) = 11 | minimum C6-saturated graph on 8 vertices, 11 edges (unique) | #57145 |
| z(10, 10; 3, 4) = 66 | bipartite, parts of size 10 and 10, 66 edges | #56650 |
| z(9, 10; 3, 4) = 60 | bipartite, parts of size 9 and 10, 60 edges | #56652 |
| z(9, 11; 3, 4) = 66 | bipartite, parts of size 9 and 11, 66 edges | #56651 |
Graph saturation for C6
For a forbidden graph F, a graph G is F-saturated when G contains no copy of F, yet adding any missing edge creates one. sat(n, F) is the minimum number of edges over all F-saturated graphs on n vertices. Here F is the 6-cycle C6, taken as a subgraph.
No exact formula for sat(n, C6) is known. Lan and Shi (2021, 2025) prove 4n/3 - 2 <= sat(n, C6) <= (4n + 1)/3 for n >= 9.
The computed chain is sat(6, C6) through sat(10, C6) = 9, 10, 11, 12, 13, an n+3 pattern. The minimum C6-saturated graph on 8 vertices, sat(8, C6) = 11, is deposited as #57145; it is the unique minimum at 11 edges (degree sequence [4,4,3,3,3,2,2,1], two triangles, non-bipartite).
Two of these values are new. sat(9, C6) = 12 and sat(10, C6) = 13 are exact, each with both certificates: the lower bound by complete exhaustive enumeration (its completeness certified by matching the graph counts in OEIS A008406, re-derived by Polya-Burnside counting as a second method), and the upper bound by a witness re-verified from its graph6 string. Both continue the n+3 pattern and sit at the top of the Lan-Shi window. There are exactly 5 non-isomorphic minima at n = 9 and 2 at n = 10. These two witnesses are verified and prepared for deposit, not yet deposited.
Saturation for K_4 and P_4
For K_4 the value is known in closed form: sat(n, K_4) = 2n - 3 (Erdos, Hajnal, and Moon, 1964). Concrete minimum K_4-saturated witnesses for n = 8, 9, 10 (13, 15, 17 edges) were computed by SAT, re-verified from their graph6 strings, and prepared for deposit.
The P_4 series is non-monotone: sat(8, P_4) = 4 is smaller than sat(7, P_4) = 5. Its minimum witnesses are small forests, so they carry little novelty. They are prepared for series completeness rather than for their own sake.
Zarankiewicz witnesses z(m, n; 3, 4)
z(m, n; 3, 4) is the maximum number of edges in an m-by-n bipartite graph whose adjacency matrix has no 3-by-4 all-ones submatrix: no 3 vertices on the m-side share 4 common neighbours. This is a one-sided, ordered condition, and it matters for how the witness is described. House of Graphs stores graphs unlabeled, so a claim about the ordered matrix has to be restated to stay true without the row and column labels. Two of these witnesses contain a K_{3,4} in the permitted 4-by-3 orientation, so calling them “K_{3,4}-free” would be false; the correct description is the matrix condition.
| Result | Witness | House of Graphs | OEIS |
|---|---|---|---|
| z(10, 10; 3, 4) = 66 | parts 10 and 10, 66 edges, no 3-by-4 all-ones submatrix; contains K_{3,4} in the permitted 4-by-3 orientation | #56650 | A006615 |
| z(9, 10; 3, 4) = 60 | parts 9 and 10, 60 edges, no 3-by-4 all-ones submatrix; contains K_{3,4} in the permitted 4-by-3 orientation | #56652 | A006622 |
| z(9, 11; 3, 4) = 66 | parts 9 and 11, 66 edges, genuinely K_{3,4}-free: no 3 vertices on either side share 4 common neighbours | #56651 | A006625 |
Each of the three certifies a value that is also a term of a classical Zarankiewicz sequence in the OEIS (originally due to N. J. A. Sloane), and the same witnesses back those OEIS extensions.
Verify
Every witness is stored as a byte-exact graph6 string and re-decoded and re-checked from scratch before it is deposited. graph6 strings can contain a literal backtick, so each is kept as raw bytes rather than typed into prose. The saturation bounds use SAT solving (CaDiCaL and Kissat, agreeing) for the upper-bound witnesses, and, for the C6 lower bounds, complete exhaustive enumeration whose completeness is certified against OEIS A008406. The Zarankiewicz witnesses are checked in both orientations, so the matrix-condition description is verified, not assumed. The full certificates and computation details are in the backing papers.
Papers
- Graph saturation for C_k, P_k, K_4, K_{2,3}: Zenodo 10.5281/zenodo.19985046.
- Three new Zarankiewicz numbers z(m, n; 3, 4): Zenodo 10.5281/zenodo.19985042.
The House of Graphs is a shared database of graphs and their invariants. Depositing a witness turns an extremal result from a number in a paper into an object anyone can fetch, decode, and check: a small permanent addition to a commons that outlasts the project that produced it.