back to table · edit · history · where entries came from · files · download
13672 bytes, as of the version from 2026-09-23 07:06 (current). Recorded here, not run.
"""Zarankiewicz numbers z(m,n;s,t) -- numberdb.org/T442
For positive integers m, n, s and t, this stores the maximum number of edges in
a subgraph of K_{m,n} with no K_{s,t} subgraph. The current range is diagonal:
z(m,n;s,s), stored with m <= n.
Run it with SageMath:
$ sage -pip install numberdb # once
$ sage -python generate.py # check the table against this code
$ sage -python generate.py --publish # fill the draft, with NUMBERDB_API_KEY set
The values are exact integers, except for z(32,32;2,2), which is the integer
interval [189, 190] as written in the source table. The tables for 3 <= s <= 6
are parsed from the source LaTeX rows below; only entries marked as bold in the
paper are stored, because the unbolded entries are one-sided upper bounds.
"""
import os
import re
import sys
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
TABLE = os.environ.get("NUMBERDB_TABLE", "T442")
Z_N_2 = {
1: 1,
2: 3,
3: 6,
4: 9,
5: 12,
6: 16,
7: 21,
8: 24,
9: 29,
10: 34,
11: 39,
12: 45,
13: 52,
14: 56,
15: 61,
16: 67,
17: 74,
18: 81,
19: 88,
20: 96,
21: 105,
22: 108,
23: 115,
24: 122,
25: 130,
26: 138,
27: 147,
28: 156,
29: 165,
30: 175,
31: 186,
32: "[189, 190]",
}
SOURCE_ROWS = {
3: r"""
6 & \mathbf{26}^\ast & \mathbf{29} & \mathbf{32} & \mathbf{36}^\ast & \mathbf{39}^\ast & \mathbf{42} & \mathbf{45}^\ast & \mathbf{48}^\ast & \mathbf{50} & \mathbf{53} & \mathbf{56} & \mathbf{58} & 61\\\hline
7 & & \mathbf{33}^\ast & \mathbf{37}^\ast & \mathbf{40} & \mathbf{44}^\ast & \mathbf{47} & \mathbf{50} & \mathbf{53} & \mathbf{56} & \mathbf{60}^\ast & \mathbf{63}^\ast & \mathbf{66} & 69 \\\cline{0-0}\cline{3-14}
8 & \multicolumn{2}{|c|}{} & \mathbf{42}^\ast & \mathbf{45} & \mathbf{50}^\ast & \mathbf{53} & \mathbf{57}^\ast & \mathbf{60} & \mathbf{64}^\ast & \mathbf{67} & \mathbf{70} & \mathbf{74}^\ast & 78 \\\cline{0-0}\cline{4-14}
9 & \multicolumn{3}{|c|}{} & \mathbf{49} & \mathbf{54} & \mathbf{59}^\ast & \mathbf{64}^\ast & \mathbf{67}^\ast & \mathbf{70} & \mathbf{73} & \mathbf{77} & \mathbf{81} & 85 \\\cline{0-0}\cline{5-14}
10 & \multicolumn{4}{|c|}{} & \mathbf{60}^\dagger & \mathbf{64}^\ast & \mathbf{68} & \mathbf{73}^\ast & \mathbf{77} & \mathbf{81}^\ast & \mathbf{85}^\ast & \mathbf{90}^\ast & 94 \\\cline{0-0}\cline{6-14}
11 & \multicolumn{5}{|c|}{} & \mathbf{69}^\ast & \mathbf{74} & \mathbf{80} & \mathbf{84} & \mathbf{88} & \mathbf{92} & \mathbf{96} & 101\\\cline{0-0}\cline{7-14}
12 & \multicolumn{6}{|c|}{} & \mathbf{80} & \mathbf{86}^\ast & \mathbf{91}^\ast & \mathbf{96} & \mathbf{99} & \mathbf{103}^\ast & 109 \\\cline{0-0}\cline{8-14}
13 & \multicolumn{7}{|c|}{} & \mathbf{92}^\ast & \mathbf{98}^\ast & \mathbf{104}^\ast & \mathbf{107} & \mathit{110} & 116\\\cline{0-0}\cline{9-14}
14 & \multicolumn{8}{|c|}{} & \mathbf{105}^\ast & \mathbf{112}^\ast & \mathbf{115}^\ast & 118 & 124 \\\cline{0-0}\cline{10-14}
15 & \multicolumn{9}{|c|}{} & \mathbf{120}^\dagger & \mathbf{123}^\ast & 126 & 132\\\cline{0-0}\cline{11-14}
16 & \multicolumn{10}{|c|}{} & \mathbf{128}^\ast & \it{133} & 140 \\\cline{0-0}\cline{12-14}
17 & \multicolumn{11}{|c|}{} & 141 & 148 \\\cline{0-0}\cline{13-14}
18 & \multicolumn{12}{|c|}{} & 156 \\\cline{0-0}\cline{14-14}
""",
4: r"""
6 & \mathbf{31}^\ast & \mathbf{36}^\ast & \mathbf{39} & \mathbf{43} & \mathbf{47} & \mathbf{51} & \mathbf{55} & \mathbf{59} & \mathbf{63} & \mathbf{67} & \mathbf{71}^\ast & \mathbf{75}^\ast & \mathbf{78}\\\hline
7 & & \mathbf{42}^\dagger & \mathbf{45} & \mathbf{49} & \mathbf{54} & \mathbf{58} & \mathbf{63} & \mathbf{68}^\ast & \mathbf{72} & \mathbf{77} & \mathbf{82}^\ast & \mathbf{87^\ast} & \mathbf{90}\\\cline{0-0}\cline{3-14}
8 & \multicolumn{2}{|c|}{} & \mathbf{51}^\ast & \mathbf{55} & \mathbf{60} & \mathbf{65} & \mathbf{70} & \mathbf{75} & \mathbf{80} & \mathbf{85} & \mathbf{90} & \mathbf{95}^\ast & \mathbf{99} \\\cline{0-0}\cline{4-14}
9 & \multicolumn{3}{|c|}{} & \mathbf{61} & \mathbf{67} & \mathbf{72} & \mathbf{78}^\ast & \mathbf{84}^\ast & \mathbf{88} & \mathbf{94} & \mathbf{99} & \mathbf{104} & \mathit{109} \\\cline{0-0}\cline{5-14}
10 & \multicolumn{4}{|c|}{} & \mathbf{74}^\ast & \mathbf{79} & \mathbf{86}^\ast & \mathbf{93}^\ast & \mathbf{97} & \mathbf{103} & \mathbf{109} & \mathbf{115} & \mathbf{120} \\\cline{0-0}\cline{6-14}
11 & \multicolumn{5}{|c|}{} & \mathbf{86} & \mathbf{93}^\ast & \mathbf{100}^\ast & \mathbf{105} & \mathbf{111} & \mathit{117} & 124 & 131 \\\cline{0-0}\cline{7-14}
12 & \multicolumn{6}{|c|}{} & 101 & 109 & 114 & 121 & 127 & 134 & 141 \\\cline{0-0}\cline{8-14}
13 & \multicolumn{7}{|c|}{} & 118 & 123 & 131 & 137 & 145 & 152\\\cline{0-0}\cline{9-14}
14 & \multicolumn{8}{|c|}{} & 132 & 141 & 147 & 156 & 163 \\\cline{0-0}\cline{10-14}
15 & \multicolumn{9}{|c|}{} & 151 & 157 & 166 & 174\\\cline{0-0}\cline{11-14}
16 & \multicolumn{10}{|c|}{} & 167 & 177 & 185\\\cline{0-0}\cline{12-14}
17 & \multicolumn{11}{|c|}{} & 188 & 196 \\\cline{0-0}\cline{13-14}
18 & \multicolumn{12}{|c|}{} & 207 \\\cline{0-0}\cline{14-14}
""",
5: r"""
6 & \mathbf{33}^\ast & \mathbf{38}^\ast & \mathbf{43}^\ast & \mathbf{48}^\ast & \mathbf{52} & \mathbf{57} & \mathbf{62} & \mathbf{67}^\ast & \mathbf{72}^\ast & \mathbf{76} & \mathbf{81} & \mathbf{86} & 91 \\\hline
7 & & \mathbf{44}^\ast & \mathbf{50}^\ast & \mathbf{56}^\ast & \mathbf{60} & \mathbf{66} & \mathbf{72} & \mathbf{78}^\ast & \mathbf{84}^\dagger & \mathbf{88} & \mathbf{92}^\ast & \mathbf{96} & 101\\\cline{0-0}\cline{3-14}
8 & \multicolumn{2}{|c|}{} & \mathbf{57}^\ast & \mathbf{64}^\ast & \mathbf{68} & \mathbf{74} & \mathbf{80} & \mathbf{86}^\ast & \mathbf{92}^\ast & \mathbf{97} & \mathbf{103} & \mathbf{109} & 115\\\cline{0-0}\cline{4-14}
9 & \multicolumn{3}{|c|}{} & \mathbf{72}^\dagger & \mathbf{76} & \mathbf{82} & \mathbf{88} & \mathbf{95} & \mathbf{101} & \mathbf{108} & \mathbf{114} & \mathbf{121} & 128 \\\cline{0-0}\cline{5-14}
10 & \multicolumn{4}{|c|}{} & \mathbf{84}^\ast & \mathbf{90} & \mathbf{97} & \mathbf{104} & \mathbf{110} & \mathbf{117} & \mathbf{124} & \mathbf{131} & 138 \\\cline{0-0}\cline{6-14}
11 & \multicolumn{5}{|c|}{} & \mathbf{98} & \mathbf{106} & \mathbf{113} & \mathbf{120} & \mathbf{127} & \mathbf{135}^\ast & \mathbf{142} & 150 \\\cline{0-0}\cline{7-14}
12 & \multicolumn{6}{|c|}{} & \mathbf{114} & \mathbf{122} & \mathbf{130} & \mathbf{138} & \mathit{146} & \mathbf{154}^\ast & 163 \\\cline{0-0}\cline{8-14}
13 & \multicolumn{7}{|c|}{} & \mathbf{132}^\ast & \mathbf{140} & \mathbf{149}^\ast & \mathit{156} & \mathit{165} & 174 \\\cline{0-0}\cline{9-14}
14 & \multicolumn{8}{|c|}{} & \mathbf{150}^\ast & \mathbf{160}^\ast & \mathit{168} & \mathit{177} & 187 \\\cline{0-0}\cline{10-14}
15 & \multicolumn{9}{|c|}{} & \mathbf{171}^\ast & \mathit{180} & \mathit{189} & 200 \\\cline{0-0}\cline{11-14}
16 & \multicolumn{10}{|c|}{} & \mathbf{192}^\dagger & \mathit{201} & 212 \\\cline{0-0}\cline{12-14}
17 & \multicolumn{11}{|c|}{} & \mathit{213} & 225 \\\cline{0-0}\cline{13-14}
18 & \multicolumn{12}{|c|}{} & 238 \\\cline{0-0}\cline{14-14}
""",
6: r"""
6 & \mathbf{35}^\ast & \mathbf{40} & \mathbf{45} & \mathbf{50} & \mathbf{55} & \mathbf{60} & \mathbf{65} & \mathbf{70} & \mathbf{75} & \mathbf{80} & \mathbf{85} & \mathbf{90} & \mathbf{95}\\\hline
7 & & \mathbf{46}^\ast & \mathbf{52}^\ast & \mathbf{58}^\ast & \mathbf{64}^\ast & \mathbf{70}^\ast & \mathbf{75} & \mathbf{81} & \mathbf{87} & \mathbf{93} & \mathbf{99}^\ast & \mathbf{105}^\ast & \mathbf{110} \\\cline{0-0}\cline{3-14}
8 & \multicolumn{2}{|c|}{} & \mathbf{59}^\ast & \mathbf{66}^\ast & \mathbf{73}^\ast & \mathbf{80}^\ast & \mathbf{85} & \mathbf{92} & \mathbf{99} & \mathbf{106} & \mathbf{113}^\ast & \mathbf{120}^\ast & \mathbf{125} \\\cline{0-0}\cline{4-14}
9 & \multicolumn{3}{|c|}{} & \mathbf{74}^\ast & \mathbf{82}^\ast & \mathbf{90}^\ast & \mathbf{95} & \mathbf{102} & \mathbf{109} & \mathbf{116} & \mathbf{123} & \mathbf{130} & \mathbf{137} \\\cline{0-0}\cline{5-14}
10 & \multicolumn{4}{|c|}{} & \mathbf{95}^\ast & \mathbf{100}^\ast & \mathbf{105} & \mathbf{112} & \mathbf{120} & \mathbf{127} & \mathbf{135} & \mathbf{142} & \mathbf{150} \\\cline{0-0}\cline{6-14}
11 & \multicolumn{5}{|c|}{} & \mathbf{110}^\ast & \mathbf{115} & \mathbf{122} & \mathbf{130} & \mathbf{138} & \mathbf{147} & \mathbf{155} & \mathbf{163}\\\cline{0-0}\cline{7-14}
12 & \multicolumn{6}{|c|}{} & \mathbf{125}^\ast & \mathbf{132} & \mathbf{141} & \mathbf{150}^\ast & \mathbf{158} & \mathbf{167} & \mathbf{176} \\\cline{0-0}\cline{8-14}
13 & \multicolumn{7}{|c|}{} & \mathbf{142} & \mathbf{152}^\ast & \mathbf{161} & \mathbf{170} & \mathbf{180} & \mathbf{189}\\\cline{0-0}\cline{9-14}
14 & \multicolumn{8}{|c|}{} & \mathbf{162} & \mathbf{172} & \mathit{182} & \mathbf{192}^\ast & \mathit{202} \\\cline{0-0}\cline{10-14}
15 & \multicolumn{9}{|c|}{} & \mathbf{184}^\ast & 195 & 205 & 216\\\cline{0-0}\cline{11-14}
16 & \multicolumn{10}{|c|}{} & 208 & 218 & 230 \\\cline{0-0}\cline{12-14}
17 & \multicolumn{11}{|c|}{} & 231 & 244 \\\cline{0-0}\cline{13-14}
18 & \multicolumn{12}{|c|}{} & 258 \\\cline{0-0}\cline{14-14}
""",
}
def _key_from_stdin():
if os.environ.get("NUMBERDB_KEY_FROM_STDIN") != "1":
return
token = sys.stdin.read().strip()
if "=" in token and token.split("=", 1)[0].isupper():
token = token.split("=", 1)[1].strip().strip("'\"")
if token:
os.environ["NUMBERDB_API_KEY"] = token
def _expand_multicolumns(cells):
expanded = []
for cell in cells:
found = re.search(r"\\multicolumn\{(\d+)\}", cell)
if found:
expanded.extend([""] * int(found.group(1)))
else:
expanded.append(cell)
return expanded
def _split_rows(text):
for raw in text.splitlines():
row = raw.strip()
if not row or "&" not in row:
continue
row = row.split(r"\\", 1)[0].strip()
first, rest = row.split("&", 1)
first = first.strip()
if not first.isdigit():
continue
yield int(first), _expand_multicolumns(rest.split("&"))
def _bold_value(cell):
found = re.search(r"\\mathbf\{\\?(\d+)", cell)
if not found:
return None
return int(found.group(1))
def _source_entries():
for n, value in sorted(Z_N_2.items()):
yield (n, n, 2, 2), value
for s, rows in sorted(SOURCE_ROWS.items()):
for m, cells in _split_rows(rows):
if len(cells) != 13:
raise ValueError("row m=%s, s=%s has %s cells" % (m, s, len(cells)))
for offset, cell in enumerate(cells):
n = 6 + offset
value = _bold_value(cell)
if value is not None:
yield (m, n, s, s), value
def _entries():
entries = dict(_source_entries())
if len(entries) != len(list(_source_entries())):
raise ValueError("duplicate Zarankiewicz entry")
return entries
ENTRIES = _entries()
def _as_record_value(value):
if isinstance(value, str):
return {
"number": value,
"comment": (
r"The source writes $189/190$ for the first open diagonal "
r"$s=2$ case."
),
}
return ZZ(value)
def _one_full_side_value(m, n, s, t):
if m == s and n >= t:
return (s - 1) * n + t - 1
if n == t and m >= s:
return (t - 1) * m + s - 1
return None
def _check_identities():
for (m, n, s, t), value in ENTRIES.items():
if not (m <= n and s == t):
raise AssertionError("entry is not stored as a diagonal m<=n value")
if isinstance(value, str):
continue
expected = _one_full_side_value(m, n, s, t)
if expected is not None and expected != value:
raise AssertionError(
"one-full-side formula gives %s for %s, stored %s"
% (expected, (m, n, s, t), value)
)
for (m, n, s, t), value in ENTRIES.items():
if isinstance(value, str):
continue
left = ENTRIES.get((m - 1, n, s, t))
below = ENTRIES.get((m, n - 1, s, t))
for previous in (left, below):
if isinstance(previous, int) and previous > value:
raise AssertionError(
"monotonicity fails at %s with previous %s" % ((m, n, s, t), previous)
)
class ZarankiewiczNumbers(numberdb.Generator):
table = TABLE
parameters = ("m", "n", "s", "t")
type = "Z"
rigour = "proven"
def enumerate(self):
for m, n, s, t in sorted(ENTRIES, key=lambda item: (item[2], item[3], item[0], item[1])):
yield {"m": str(m), "n": str(n), "s": str(s), "t": str(t)}
def value(self, params, digits=None):
key = tuple(int(params[name]) for name in self.parameters)
return _as_record_value(ENTRIES[key])
if __name__ == "__main__":
_check_identities()
_key_from_stdin()
generator = ZarankiewiczNumbers()
if os.environ.get("NUMBERDB_PUBLISH") == "1" or "--publish" in sys.argv:
print(generator.publish(message="transcribed exact Zarankiewicz values"))
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)