NumberDB$^\beta$ Advanced search Tags Tables Help Login
Zarankiewicz numbers $z(m,n;s,t)$
edit · history · discussion · files · short url · combinatorics sequence
Numbers
$m$
$n$
$s$
$t$ 
$z(m,n;s,t)$
1
1
2
2:
1
2
2
2
2:
3
3
3
2
2:
6
4
4
2
2:
9
5
5
2
2:
12
6
6
2
2:
16
6
6
3
3:
26
6
6
4
4:
31
6
6
5
5:
33
6
6
6
6:
35
6
7
3
3:
29
6
7
4
4:
36
6
7
5
5:
38
6
7
6
6:
40
6
8
3
3:
32
6
8
4
4:
39
6
8
5
5:
43
6
8
6
6:
45
6
9
3
3:
36
6
9
4
4:
43
6
9
5
5:
48
6
9
6
6:
50
6
10
3
3:
39
6
10
4
4:
47
6
10
5
5:
52
6
10
6
6:
55
6
11
3
3:
42
6
11
4
4:
51
6
11
5
5:
57
6
11
6
6:
60
6
12
3
3:
45
6
12
4
4:
55
6
12
5
5:
62
6
12
6
6:
65
6
13
3
3:
48
6
13
4
4:
59
6
13
5
5:
67
6
13
6
6:
70
6
14
3
3:
50
6
14
4
4:
63
6
14
5
5:
72
6
14
6
6:
75
6
15
3
3:
53
6
15
4
4:
67
6
15
5
5:
76
6
15
6
6:
80
6
16
3
3:
56
6
16
4
4:
71
6
16
5
5:
81
6
16
6
6:
85
6
17
3
3:
58
6
17
4
4:
75
6
17
5
5:
86
6
17
6
6:
90
6
18
4
4:
78
6
18
6
6:
95
7
7
2
2:
21
7
7
3
3:
33
7
7
4
4:
42
7
7
5
5:
44
7
7
6
6:
46
7
8
3
3:
37
7
8
4
4:
45
7
8
5
5:
50
7
8
6
6:
52
7
9
3
3:
40
7
9
4
4:
49
7
9
5
5:
56
7
9
6
6:
58
7
10
3
3:
44
7
10
4
4:
54
7
10
5
5:
60
7
10
6
6:
64
7
11
3
3:
47
7
11
4
4:
58
7
11
5
5:
66
7
11
6
6:
70
7
12
3
3:
50
7
12
4
4:
63
7
12
5
5:
72
7
12
6
6:
75
7
13
3
3:
53
7
13
4
4:
68
7
13
5
5:
78
7
13
6
6:
81
7
14
3
3:
56
7
14
4
4:
72
7
14
5
5:
84
7
14
6
6:
87
7
15
3
3:
60
7
15
4
4:
77
7
15
5
5:
88
7
15
6
6:
93
7
16
3
3:
63
7
16
4
4:
82
7
16
5
5:
92
7
16
6
6:
99
7
17
3
3:
66
7
17
4
4:
87
7
17
5
5:
96
7
17
6
6:
105
7
18
4
4:
90
7
18
6
6:
110
8
8
2
2:
24
8
8
3
3:
42
8
8
4
4:
51
8
8
5
5:
57
8
8
6
6:
59
8
9
3
3:
45
8
9
4
4:
55
8
9
5
5:
64
8
9
6
6:
66
8
10
3
3:
50
8
10
4
4:
60
8
10
5
5:
68
8
10
6
6:
73
8
11
3
3:
53
8
11
4
4:
65
8
11
5
5:
74
8
11
6
6:
80
8
12
3
3:
57
8
12
4
4:
70
8
12
5
5:
80
8
12
6
6:
85
8
13
3
3:
60
8
13
4
4:
75
8
13
5
5:
86
8
13
6
6:
92
8
14
3
3:
64
8
14
4
4:
80
8
14
5
5:
92
8
14
6
6:
99
8
15
3
3:
67
8
15
4
4:
85
8
15
5
5:
97
8
15
6
6:
106
8
16
3
3:
70
8
16
4
4:
90
8
16
5
5:
103
8
16
6
6:
113
8
17
3
3:
74
8
17
4
4:
95
8
17
5
5:
109
8
17
6
6:
120
8
18
4
4:
99
8
18
6
6:
125
9
9
2
2:
29
9
9
3
3:
49
9
9
4
4:
61
9
9
5
5:
72
9
9
6
6:
74
9
10
3
3:
54
9
10
4
4:
67
9
10
5
5:
76
9
10
6
6:
82
9
11
3
3:
59
9
11
4
4:
72
9
11
5
5:
82
9
11
6
6:
90
9
12
3
3:
64
9
12
4
4:
78
9
12
5
5:
88
9
12
6
6:
95
9
13
3
3:
67
9
13
4
4:
84
9
13
5
5:
95
9
13
6
6:
102
9
14
3
3:
70
9
14
4
4:
88
9
14
5
5:
101
9
14
6
6:
109
9
15
3
3:
73
9
15
4
4:
94
9
15
5
5:
108
9
15
6
6:
116
9
16
3
3:
77
9
16
4
4:
99
9
16
5
5:
114
9
16
6
6:
123
9
17
3
3:
81
9
17
4
4:
104
9
17
5
5:
121
9
17
6
6:
130
9
18
6
6:
137
10
10
2
2:
34
10
10
3
3:
60
10
10
4
4:
74
10
10
5
5:
84
10
10
6
6:
95
10
11
3
3:
64
10
11
4
4:
79
10
11
5
5:
90
10
11
6
6:
100
10
12
3
3:
68
10
12
4
4:
86
10
12
5
5:
97
10
12
6
6:
105
10
13
3
3:
73
10
13
4
4:
93
10
13
5
5:
104
10
13
6
6:
112
10
14
3
3:
77
10
14
4
4:
97
10
14
5
5:
110
10
14
6
6:
120
10
15
3
3:
81
10
15
4
4:
103
10
15
5
5:
117
10
15
6
6:
127
10
16
3
3:
85
10
16
4
4:
109
10
16
5
5:
124
10
16
6
6:
135
10
17
3
3:
90
10
17
4
4:
115
10
17
5
5:
131
10
17
6
6:
142
10
18
4
4:
120
10
18
6
6:
150
11
11
2
2:
39
11
11
3
3:
69
11
11
4
4:
86
11
11
5
5:
98
11
11
6
6:
110
11
12
3
3:
74
11
12
4
4:
93
11
12
5
5:
106
11
12
6
6:
115
11
13
3
3:
80
11
13
4
4:
100
11
13
5
5:
113
11
13
6
6:
122
11
14
3
3:
84
11
14
4
4:
105
11
14
5
5:
120
11
14
6
6:
130
11
15
3
3:
88
11
15
4
4:
111
11
15
5
5:
127
11
15
6
6:
138
11
16
3
3:
92
11
16
5
5:
135
11
16
6
6:
147
11
17
3
3:
96
11
17
5
5:
142
11
17
6
6:
155
11
18
6
6:
163
12
12
2
2:
45
12
12
3
3:
80
12
12
5
5:
114
12
12
6
6:
125
12
13
3
3:
86
12
13
5
5:
122
12
13
6
6:
132
12
14
3
3:
91
12
14
5
5:
130
12
14
6
6:
141
12
15
3
3:
96
12
15
5
5:
138
12
15
6
6:
150
12
16
3
3:
99
12
16
6
6:
158
12
17
3
3:
103
12
17
5
5:
154
12
17
6
6:
167
12
18
6
6:
176
13
13
2
2:
52
13
13
3
3:
92
13
13
5
5:
132
13
13
6
6:
142
13
14
3
3:
98
13
14
5
5:
140
13
14
6
6:
152
13
15
3
3:
104
13
15
5
5:
149
13
15
6
6:
161
13
16
3
3:
107
13
16
6
6:
170
13
17
6
6:
180
13
18
6
6:
189
14
14
2
2:
56
14
14
3
3:
105
14
14
5
5:
150
14
14
6
6:
162
14
15
3
3:
112
14
15
5
5:
160
14
15
6
6:
172
14
16
3
3:
115
14
17
6
6:
192
15
15
2
2:
61
15
15
3
3:
120
15
15
5
5:
171
15
15
6
6:
184
15
16
3
3:
123
16
16
2
2:
67
16
16
3
3:
128
16
16
5
5:
192
17
17
2
2:
74
18
18
2
2:
81
19
19
2
2:
88
20
20
2
2:
96
21
21
2
2:
105
22
22
2
2:
108
23
23
2
2:
115
24
24
2
2:
122
25
25
2
2:
130
26
26
2
2:
138
27
27
2
2:
147
28
28
2
2:
156
29
29
2
2:
165
30
30
2
2:
175
31
31
2
2:
186
32
32
2
2:
[189, 190] †
comment: The exact value is not known; [1] records this first open diagonal $s=2$ case as $189$ or $190$.
Definition
The Zarankiewicz number $z(m,n;s,t)$ [1] [2] is the maximum number of edges in a subgraph of $K_{m,n}$ that contains no copy of $K_{s,t}$ as a subgraph, with the $s$ vertices of $K_{s,t}$ in the part of size $m$ and the $t$ vertices in the part of size $n$.
Parameters
$m$
—   left part size ($m\geq 1$)
$n$
—   right part size ($n\geq 1$)
$s$
—   left forbidden part size ($s\geq 1$)
$t$
—   right forbidden part size ($t\geq 1$)
Formulas
(1)
$z(m,n;s,t)=z(n,m;t,s)$.
(2)
If $m<s$ or $n<t$, then $z(m,n;s,t)=mn$.
(3)
If $m=s$ and $n\geq t$, then $z(s,n;s,t)=(s-1)n+t-1$. By symmetry, if $n=t$ and $m\geq s$, then $z(m,t;s,t)=(t-1)m+s-1$.
Comments
(4)
The appendix of [1] writes $z(m,n;s)$ for $z(m,n;s,s)$ and $z(n;s)$ for $z(n,n;s,s)$. Every entry currently stored is diagonal in this sense.
(5)
The diagonal entries are stored with $m\leq n$, using $z(m,n;s,s)=z(n,m;s,s)$.
(6)
The $s=t=2$ diagonal sequence stored here is OEIS A072567 [3]. OEIS A001197 [4] tabulates the least number of ones that forces a $2\times 2$ all-one submatrix in an $n\times n$ zero-one matrix, which is $z(n,n;2,2)+1$.
(7)
The appendix also gives one-sided upper bounds for diagonal values. Those rows are omitted unless the source marks the value as exact or gives an explicit two-sided range.
(8)
In [1], bold entries in the tables for $3\leq s\leq6$ are exact values; unbolded entries are upper bounds.
References
[1]
Alex F. Collins, Alexander W. N. Riasanovsky, John C. Wallace and Stanislaw P. Radziszowski, "Zarankiewicz Numbers and Bipartite Ramsey Numbers", Journal of Algorithms and Computation 47, 63-78, 2016. (arXiv)
Links
Similar tables
Diagonal Ramsey numbers —   also records a Ramsey-type graph quantity known exactly only in small cases; [1] uses Zarankiewicz numbers to bound bipartite Ramsey numbers, the analogous thresholds for edge-coloured complete bipartite graphs
Ramsey numbers of complete graphs —   belongs to the same Ramsey-theory area; this table stores an extremal function rather than a least-forcing threshold
Data properties
Entries are of type: integer
Sources of data: [1]
How well the digits are known: proven
How they were obtained:

The exact integers and the interval $[189,190]$ are transcribed from the appendix tables in [1]. The diagonal values $z(n,n;2,2)$ come from Table 3. For $3\leq s\leq6$, the entries are precisely the values marked in bold in Tables 4 through 7.

more

The generator checks the source transcription against a separately parsed copy of those LaTeX tables, checks the symmetry convention on every entry, and checks the formula for the rows with one part equal to the forbidden part size. The interval width records uncertainty about the exact integer, not numerical error.

Table is complete: no (it holds the diagonal values $z(n,n;2,2)$ for $1\leq n\leq32$ from Table 3 of [1], and the exact diagonal entries marked in bold for $3\leq s\leq6$ and $6\leq m\leq n\leq18$ in Tables 4 through 7; one-sided upper bounds in those tables are not entries)


API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.