Zarankiewicz問題

同義語：Zarankiewicz problemZarankiewicz's problem

概要

前提知識: 二部グラフ, 完全二部グラフ, 二項係数, 射影平面

Zarankiewicz 問題（Zarankiewicz problem）とは、成分が $0$ か $1$ の $m\times n$ 行列が、$s$ 個の行と $t$ 個の列の交わりの成分がすべて $1$ になる部分行列を含まないとき、$1$ の個数は最大でいくつになれるか、を問う問題である。その最大値を $z(m,n;s,t)$ と書く。K. Zarankiewicz は 1951 年に $n\le6$ での $z(n,n;3,3)$ を求める問題を出し、一般の $m,n,s,t$ の場合も含めてこの名で呼ばれるようになった（FS13 p. 24）。二部グラフの言葉では、部の大きさが $m,n$ の二部グラフが、一方の部の $s$ 頂点と他方の部の $t$ 頂点からなる完全二部グラフを含まないときの辺の本数の最大値である。
正確な値が分かっている場合は少ない。一般の上界は Kővári–Sós–Turánの定理が与え、この記事では問題そのものを扱う。列の数が行の数に比べて十分大きいときの正確な値（Čulík の定理）を証明し、$s=t=2$ では上界とその等号が成り立つ行列が射影平面の接続行列に限ることを示して、$n\le8$ の $z(n,n;2,2)$ を決める。最後に $K_{3,3}$ の場合と未解決の状況を述べる。

定義

$m,n,s,t\ge1$ を整数とする。成分が $0$ か $1$ の行列を $0$-$1$ 行列 という。

Zarankiewicz数

$m\times n$ の $0$-$1$ 行列 $A=(a_{ij})$ が $s\times t$ の全 $1$ 部分行列を含む とは、$s$ 個の行の集合 $S$ と $t$ 個の列の集合 $T$ で、すべての $i\in S$、$j\in T$ について $a_{ij}=1$ となるものがあることをいう。$s\times t$ の全 $1$ 部分行列を含まない $m\times n$ の $0$-$1$ 行列の $1$ の個数の最大値を $z(m,n;s,t)$ と書き、Zarankiewicz 数 という。$z(m,n;s,t)$ を求める問題を Zarankiewicz 問題 という。

$s$ は行の側、$t$ は列の側の大きさである。$s>m$ または $t>n$ なら選べる部分行列がないので、$z(m,n;s,t)=mn$ である。
二部グラフで言い換える。頂点の集合が $U\sqcup V$（$\lvert U\rvert=m$、$\lvert V\rvert=n$）で、辺がすべて $U$ と $V$ を結ぶグラフ $G$ を、部 $U,V$ を指定した二部グラフという。$U=\{u_1,\dots,u_m\}$、$V=\{v_1,\dots,v_n\}$ と番号を付け、$u_i$ と $v_j$ が隣接するとき $a_{ij}=1$ とおくと、$G$ と $m\times n$ の $0$-$1$ 行列が 1 対 1 に対応し、辺の本数は $1$ の個数になる。$s\times t$ の全 $1$ 部分行列は、$U$ の $s$ 頂点と $V$ の $t$ 頂点からなる $K_{s,t}$ にあたる。したがって $z(m,n;s,t)$ は、$U$ の側に $s$ 頂点、$V$ の側に $t$ 頂点をもつ $K_{s,t}$ を含まない、部 $U,V$ を指定した二部グラフの辺の本数の最大値である。向きを指定しているので、$s\ne t$ のとき $z(m,n;s,t)$ と $z(m,n;t,s)$ は一般に異なる（Kővári–Sós–Turánの定理の例「行と列の役割」）。

最も小さい場合

$s=1$ のとき、各行の $1$ が $t-1$ 個以下であることが条件なので $z(m,n;1,t)=m\min\{t-1,n\}$ である（Kővári–Sós–Turánの定理の例「小さい場合」）。
$z(2,2;2,2)=3$ である。$2\times2$ の行列が $2\times2$ の全 $1$ 部分行列を含まないことは、成分のどれかが $0$ であることと同じだからである。
$2\times2$ の全 $1$ 部分行列を含まないことは、相異なる 2 つの行の両方で $1$ になる列が $1$ 個以下であること、すなわち二部グラフが長さ $4$ の閉路を含まないことと同じである。

基本的な性質

$z(m,n;s,t)=z(n,m;t,s)$ である。
$m\le m'$、$n\le n'$ なら $z(m,n;s,t)\le z(m',n';s,t)$ であり、$s\le s'$、$t\le t'$ なら $z(m,n;s,t)\le z(m,n;s',t')$ である。
$K_{s,t}$ を含まない $n$ 頂点の単純グラフ $G$ について $2e(G)\le z(n,n;s,t)$ である（$e(G)$ は辺の本数）。したがって $2\operatorname{ex}(n,K_{s,t})\le z(n,n;s,t)$ である。
$z(n,n;s,s)\le\operatorname{ex}(2n,K_{s,s})$ である。

ここで $\operatorname{ex}(N,H)$ は、$H$ と同型な部分グラフをもたない $N$ 頂点の単純グラフの辺の本数の最大値（極値グラフ理論の極値数）である。

転置・零の追加・隣接行列

要点：1 は転置、2 は $0$ の行と列の追加、3 は対角成分が $0$ の隣接行列、4 は $K_{s,s}$ の二部分割が部 $U,V$ に沿うことによる。

詳細

1. 転置行列をとると、$s\times t$ の全 $1$ 部分行列と $t\times s$ の全 $1$ 部分行列が入れ替わる。

2. 前半：$m\times n$ の行列の右と下に $0$ を足して $m'\times n'$ にしても、$1$ の個数は変わらず、新しい行と列は $0$ だけなので全 $1$ 部分行列は増えない。後半：$s'\times t'$ の全 $1$ 部分行列は $s\times t$ の全 $1$ 部分行列を含むので、後者を含まない行列は前者も含まない。

3. $G$ の隣接行列 $A$（$a_{ii}=0$）の $1$ の個数は $2e(G)$ である。$A$ の行の集合 $S$ と列の集合 $T$ で全 $1$ の部分行列ができたとすると、$a_{ii}=0$ なので $S\cap T=\emptyset$ であり、$S$ と $T$ は $G$ の中で $K_{s,t}$ をなす。よって $A$ は $s\times t$ の全 $1$ 部分行列を含まない。（Kővári–Sós–Turánの定理の定理「Kővári–Sós–Turánの定理」の証明の 2 と同じ議論である。）

4. $A$ を $s\times s$ の全 $1$ 部分行列を含まない $n\times n$ の行列とし、対応する部 $U,V$ の二部グラフ $G$（$2n$ 頂点）を考える。$G$ が $K_{s,s}$ と同型な部分グラフ $K$ を含むとする。$K$ は連結で（$s\ge1$）、その二部分割の一方を $X$、他方を $Y$ とする。$x\in X$ が $U$ に属すれば、$x$ の隣接頂点は $V$ にあるので $Y\subset V$ であり、同じ理由で $X\subset U$ である。$x\in V$ なら $X\subset V$、$Y\subset U$ である。どちらの場合も、$U$ の側の $s$ 頂点と $V$ の側の $s$ 頂点が完全に結ばれ、$A$ の $s\times s$ の全 $1$ 部分行列になる。よって $G$ は $K_{s,s}$ を含まず、$e(G)\le\operatorname{ex}(2n,K_{s,s})$ である。$\square$

極値グラフ理論の命題「極値数の単調性」の 3 を $n$ から $2n$ まで繰り返すと、$n\ge2$ で $\operatorname{ex}(2n,K_{s,s})\le\frac{\binom{2n}2}{\binom n2}\operatorname{ex}(n,K_{s,s})=\frac{2(2n-1)}{n-1}\operatorname{ex}(n,K_{s,s})\le6\operatorname{ex}(n,K_{s,s})$ である。3・4 とあわせて
$$ 2\operatorname{ex}(n,K_{s,s})\le z(n,n;s,s)\le6\operatorname{ex}(n,K_{s,s})\qquad(n\ge2) $$
となり、正方形の場合の Zarankiewicz 数と $K_{s,s}$ の極値数は定数倍の違いを除いて同じ大きさである。

列が十分多いとき：Čulík の定理

列の数 $n$ が行の数 $m$ に比べて十分大きいと、$z(m,n;s,t)$ は正確に決まる（K. Čulík、1956 年。FS13 Theorem 3.28、p. 38）。

二項係数の一次の下界

整数 $s\ge1$、$d\ge0$ について $d\le(s-1)+\binom ds$ である。

$d\le s-1$ なら $\binom ds=0$ で、主張は $d\le s-1$ そのものである。$d\ge s$ のときは $\binom ds\ge d-s+1$ を $d$ についての帰納法で示す。$d=s$ では両辺とも $1$ である。$d\ge s$ で成り立てば、$0\le s-1\le d$ より $\binom d{s-1}\ge1$ なので、$\binom{d+1}s=\binom ds+\binom d{s-1}\ge(d-s+1)+1$ である。$\square$

列が多い場合の正確な値

$m\ge s\ge1$、$t\ge1$ とし、$N:=(t-1)\binom ms$ とおく。$n\ge N$ なら
$$ z(m,n;s,t)=(s-1)n+(t-1)\binom ms $$
である。

$s$ 個の行の組を列ごとに数える

上界．$A$ を $s\times t$ の全 $1$ 部分行列を含まない $m\times n$ の行列とし、第 $j$ 列の $1$ の個数を $d_j$ とする。$s$ 個の行の集合 $S$ と列 $j$ の組で、$S$ のすべての行で第 $j$ 列が $1$ であるものの個数を $X$ とする。$S$ を決めるとそのような列は $t-1$ 個以下なので $X\le(t-1)\binom ms$ であり、列 $j$ を決めると $S$ は $\binom{d_j}s$ 通りなので $X=\sum_j\binom{d_j}s$ である。lem-zp-binomial により
$$ \sum_{j=1}^nd_j\le\sum_{j=1}^n\Bigl((s-1)+\binom{d_j}s\Bigr)=(s-1)n+X\le(s-1)n+(t-1)\binom ms $$
である。
構成．$s$ 個の行の集合 $S$ のそれぞれについて、$S$ の行で $1$、ほかの行で $0$ の列を $t-1$ 本ずつ並べる。これで $N$ 本の列ができる。残りの $n-N$ 本の列は、どれも $1$ をちょうど $s-1$ 個もつ列とする（$m\ge s-1$ なので作れる）。$1$ の個数は $sN+(s-1)(n-N)=(s-1)n+N$ である。$s\times t$ の全 $1$ 部分行列があったとして、その行の集合を $S$ とすると、その $t$ 本の列はどれも $s$ 個以上の $1$ をもつので前半の列であり、$1$ の行の集合は $S$ を含む $s$ 元集合、すなわち $S$ そのものである。そのような列は $t-1$ 本しかないので矛盾する。$\square$

上界の証明は Kővári–Sós–Turánの定理の証明と同じ数え方で、凸性の代わりに lem-zp-binomial の一次の評価を使っている。$s\ge2$ のとき、等号には、どの列の $1$ の個数も $s-1$ か $s$ であることと、どの $s$ 個の行もちょうど $t-1$ 本の列で全 $1$ になることが要り、$n\ge N$ はその両方を同時にみたすための条件である。

$s=t=2$ の場合

$m\ge2$、$n\ge\binom m2$ なら $z(m,n;2,2)=n+\binom m2$ である。

完全グラフの辺と列

$m=4$、$n=6$ では $z(4,6;2,2)=6+6=12$ である。構成は、4 個の行を完全グラフ $K_4$ の頂点と見て、$K_4$ の 6 本の辺のそれぞれを、その両端の行だけが $1$ の列にしたものである。どの 2 行も、それらを結ぶ辺の列 1 本だけで共に $1$ になる。

$n< N$ では値は一般に小さくなる（ex-zp-counterexamples の 1 行目）。とくに正方形の場合 $m=n$ は、$s,t\ge2$ なら $n\ge(t-1)\binom ns$ が $n$ の小さい値でしか成り立たず（$s=t=2$ では $n\le3$）、この定理の外にある。

$s=t=2$：Reiman の上界と射影平面

$2\times2$ の全 $1$ 部分行列を含まない行列は、二部グラフでは長さ $4$ の閉路を含まないものである（ex-zp-small-cases の 3）。この場合の上界は I. Reiman（1958 年）による（FS13 Theorem 3.2、p. 25）。

Reimanの不等式

$m,n\ge1$ について
$$ z(m,n;2,2)\le\frac12\Bigl(n+\sqrt{n^2+4nm(m-1)}\Bigr) $$
である。とくに $z(n,n;2,2)\le\frac n2\bigl(1+\sqrt{4n-3}\bigr)$ である。

行の対を数えてCauchy–Schwarzの不等式を使う

$A$ を $2\times2$ の全 $1$ 部分行列を含まない $m\times n$ の行列とし、$1$ の個数を $Z$、第 $j$ 列の $1$ の個数を $d_j$ とする。相異なる 2 つの行の両方が $1$ である列は $1$ 個以下なので、行の対と列の組でその列が両方の行で $1$ であるものを数えると
$$ \sum_{j=1}^n\binom{d_j}2\le\binom m2\qquad(1) $$
である。Cauchy–Schwarzの不等式により
$$ \sum_{j=1}^nd_j^2\ge\frac1n\Bigl(\sum_{j=1}^nd_j\Bigr)^2=\frac{Z^2}n\qquad(2) $$
である。(1) と (2) から $\frac12\bigl(\frac{Z^2}n-Z\bigr)\le\frac12m(m-1)$、すなわち $Z^2-nZ-nm(m-1)\le0$ であり、この 2 次不等式を解くと主張の上界を得る。$m=n$ では根号の中が $n^2(4n-3)$ になる。$\square$

正方形の場合の上界は Kővári–Sós–Turánの定理の命題「射影平面の接続行列」の 1 と同じものであり、同じ命題の 2 は、$q$ が素数の冪で $N=q^2+q+1$ のとき、有限体 $\mathbb F_q$ の上の射影平面の点と直線の接続行列が等号 $z(N,N;2,2)=(q+1)N$ を与えることを示している。次の定理は、等号を与える行列が射影平面から来るものに限ることを示す。

等号の場合と射影平面

$n\ge2$ とし、$A$ を $2\times2$ の全 $1$ 部分行列を含まない $n\times n$ の行列で、$1$ の個数が $\frac n2\bigl(1+\sqrt{4n-3}\bigr)$ に等しいものとする。

$n=q^2+q+1$ となる整数 $q\ge1$ がある。$A$ のどの行とどの列にも $1$ がちょうど $q+1$ 個あり、相異なる 2 つの行の両方が $1$ である列はちょうど $1$ 個、相異なる 2 つの列の両方が $1$ である行はちょうど $1$ 個である。
$q\ge2$ なら、行を点、列を直線とし、$a_{ij}=1$ のとき点 $i$ が直線 $j$ の上にあると定めた組は、位数 $q$ の射影平面（公理による射影平面）である。
逆に、位数 $q\ge2$ の射影平面があれば、$N=q^2+q+1$ について $z(N,N;2,2)=(q+1)N$ であり、その接続行列が等号を与える。

二つの不等式がともに等号になる

prf-zp-reiman で $m=n$ とし、$Z$ が上界に等しいとすると、(1) と (2) がともに等号である。(2) の等号から $d_1=\dots=d_n$ であり、この共通の値を $d$ とおくと $d$ は整数である。(1) の等号は、相異なる 2 行の対の $\binom n2$ 個がどれもちょうど $1$ 本の列で両方 $1$ になることを意味する。(1) の等号を $n\binom d2=\binom n2$ と書き直すと $d(d-1)=n-1$ なので、$q:=d-1$ とおけば $n=q^2+q+1$ であり、$n\ge2$ から $q\ge1$ である。転置行列 $A^{\mathsf T}$ も $2\times2$ の全 $1$ 部分行列を含まず、$1$ の個数は同じなので、同じ議論により各行の $1$ の個数は $q+1$ で、相異なる 2 列はちょうど $1$ 個の行で両方 $1$ になる。
公理 (i)（相異なる 2 点を通る直線がただ 1 本ある）と (ii)（相異なる 2 直線の上にある点がただ 1 つある）は 1 の後半そのものである。公理 (iii) を示す。直線 $\ell$ と、その上の相異なる 2 点 $P,Q$ をとり（$\ell$ の上の点は $q+1\ge3$ 個）、$\ell$ の上にない点 $R$ をとる（点は $n>q+1$ 個）。$P$ と $R$ を通る直線、$Q$ と $R$ を通る直線、$\ell$ の 3 本はどの 2 本も 1 点ずつ（$P$、$Q$、$R$ のどれか）を共有するので、その上の点は合わせて $3(q+1)-3=3q$ 個である。$q\ge2$ なら $n-3q=(q-1)^2>0$ なので、3 本のどれの上にもない点 $T$ がある。$P,Q,R,T$ のどの 3 点も、それらのうち 2 点を通るただ 1 本の直線（$\ell$、$PR$、$QR$ のどれか）の上に残りの 1 点がないので、同じ直線の上にない。各直線の上の点は $q+1$ 個なので、位数は $q$ である（射影平面の定理「有限射影平面の位数」）。
逆向き：同じ定理により、位数 $q$ の射影平面は点と直線をそれぞれ $N$ 個もち、各直線の上に $q+1$ 個の点がある。点を行、直線を列とする接続行列は $(q+1)N$ 個の $1$ をもち、相異なる 2 点を通る直線は 1 本だけなので、$2\times2$ の全 $1$ 部分行列を含まない。$4N-3=(2q+1)^2$ なので上界は $\frac N2(2q+2)=(q+1)N$ であり、等号が成り立つ。$\square$

$4n-3$ が平方数でない $n$ では上界は整数でないので、等号は起こらない。$4n-3$ が平方数でも、$n=q^2+q+1$ の位数 $q$ の射影平面がなければ等号は起こらない。$q=1$（$n=3$）の場合は、対角成分だけが $0$ の $3\times3$ 行列 $J-I$ が等号 $z(3,3;2,2)=6$ を与えるが、これは 3 点と 2 点ずつの 3 本の「直線」からなる三角形で、公理 (iii) をみたさない（ex-zp-counterexamples の 2 行目）。

小さい値

$n\le8$ の値

$z(n,n;2,2)$ は $n=1,2,\dots,8$ について次の表の値をとる。

$n$	上界 $\lfloor\frac n2(1+\sqrt{4n-3})\rfloor$	$z(n,n;2,2)$	値を与える行列
$1$	$1$	$1$	$(1)$
$2$	$3$	$3$	成分の 1 つだけが $0$
$3$	$6$	$6$	$J-I$
$4$	$9$	$9$	Fano 平面から、一直線上にない 3 点とそのうち 2 点ずつを通る 3 直線を除く
$5$	$12$	$12$	Fano 平面から 2 点 $P,Q$ と、直線 $PQ$・$P$ を通るほかの 1 直線を除く
$6$	$16$	$16$	Fano 平面から 1 点とそれを通る 1 直線を除く
$7$	$21$	$21$	Fano平面の接続行列
$8$	$25$	$24$	$j-i\in\{0,1,3\}\pmod 8$ のとき $a_{ij}=1$ とする巡回行列

上界と、Fano平面の部分行列

上界．$n\le7$ では thm-zp-reiman の上界の整数部分である。$n=8$ で $1$ が $25$ 個の行列 $A$ があるとして矛盾を導く。$25>3\cdot8$ なので $1$ を $k\ge4$ 個もつ列 $c$ がある。$c$ で $1$ である $k$ 個の行の集合を $R$ とする。$R$ の 2 行はすでに列 $c$ で両方 $1$ なので、ほかの列は $R$ の中に $1$ を高々 1 個しかもたない。よって $R$ の行の $1$ は合わせて $k+7$ 個以下であり、残りの $8-k$ 行には $1$ が $18-k$ 個以上ある。この $8-k$ 行では列 $c$ は $0$ なので、その $1$ はほかの 7 列にある。第 $j$ 列のこれらの行での $1$ の個数を $e_j$ とすると、prf-zp-reiman の (1) と同じく $\sum_j\binom{e_j}2\le\binom{8-k}2$ である。一方 $\binom e2\ge e-1$（$e\ge0$）なので $\sum_j\binom{e_j}2\ge(18-k)-7=11-k$ である。$k=4,5,6,7,8$ で $11-k$ は $7,6,5,4,3$、$\binom{8-k}2$ は $6,3,1,0,0$ であり、どの場合も矛盾する。
構成．Fano 平面 $\mathbb P^2(\mathbb F_2)$ は位数 $2$ の射影平面で、7 点・7 直線をもち、各直線の上に 3 点、各点を通る直線が 3 本ある（射影平面の例「Fano 平面」）。その接続行列から行の集合 $R$ と列の集合 $C$ を除いた行列は、部分行列なので $2\times2$ の全 $1$ 部分行列を含まず、$1$ の個数は $21-3\lvert R\rvert-3\lvert C\rvert+(R\times C\text{ の中の }1\text{ の個数})$ である。$n=6$ では除く点が除く直線の上にあるので $21-3-3+1=16$ である。$n=5$ では $R\times C$ の中の $1$ は $P,Q\in PQ$ と $P$ の 3 個なので $21-6-6+3=12$ である。$n=4$ では、3 直線のそれぞれが 3 点のうちちょうど 2 点を通るので $21-9-9+6=9$ である。
$n=8$ の巡回行列の各行には $1$ が 3 個ある。相異なる行 $i,i'$ がともに列 $j$ で $1$ なら、$x:=j-i$ と $y:=j-i'$ が $\{0,1,3\}$ に属し $x-y=i'-i\ne0$ である。$\{0,1,3\}$ の相異なる 2 元の差は $\pm1,\pm2,\pm3$ で、$8$ を法として互いに異なるので、$i'-i$ から $(x,y)$ がただ 1 つ決まり、$j=i+x$ も決まる。よって 2 行が共に $1$ になる列は 1 個以下である。$n\le3$ の行列は直接確かめられる。$\square$

$n=8$ の巡回行列と同じ考え方で、$\mathbb Z/n\mathbb Z$ の部分集合 $D$ で相異なる 2 元の差がすべて異なるものから、$j-i\in D$ のとき $a_{ij}=1$ とすれば、$z(n,n;2,2)\ge\lvert D\rvert n$ が得られる。$n=7$ で $D=\{0,1,3\}$ とすると、差は $0$ でない剰余類をちょうど 1 回ずつ尽くすので、$1$ が $21$ 個の行列になる。これは上界の等号の場合なので、thm-zp-equality により位数 $2$ の射影平面の接続行列である。

$K_{3,3}$ と一般の場合

この節の主張は、Kővári–Sós–Turánの定理から引くものを除き、この記事では証明しない。
上界．Kővári–Sós–Turánの定理の定理「Kővári–Sós–Turánの定理」の 1 により、すべての $m,n,s,t\ge1$ で
$$ z(m,n;s,t)\le(t-1)^{1/s}\,m\,n^{1-1/s}+(s-1)\,n $$
である。Z. Füredi（1996 年）はこれを、$m\ge s$、$n\ge t$、$t\ge s\ge2$ のとき
$$ z(m,n;s,t)\le(t-s+1)^{1/s}\,m\,n^{1-1/s}+(s-1)\,n^{2-2/s}+(s-2)\,m $$
に改良した（FS13 Theorem 3.19、p. 33）。$s=t$ では主要項の係数が $(s-1)^{1/s}$ から $1$ に下がる。$s=t=3$ では $z(n,n;3,3)\le n^{5/3}+2n^{4/3}+n$ である。
$K_{3,3}$ の下界．W. G. Brown（1966 年）は、奇素数 $p$ について $\mathbb F_p^3$ の点を頂点とし、$(x-x')^2+(y-y')^2+(z-z')^2=d$ のとき 2 点を結ぶグラフ（$d\ne0$ は $p$ を $4$ で割った余りに応じて平方剰余か平方非剰余にとる）が、$K_{3,3}$ を含まない $(p^2-p)$-正則グラフであることを示した（FS13 Construction 3.20、p. 33）。3 次元ユークリッド空間で、相異なる 3 点のすべてから距離 $1$ にある点が高々 2 個であることの、有限体での類似である（FS13 p. 34、Zha23 定理 1.10.5、pp. 41–42）。これから、すべての $n$ について $\operatorname{ex}(n,K_{3,3})\ge\bigl(\frac12-o(1)\bigr)n^{5/3}$ が従う（同所）。prop-zp-basic の 3 と Füredi の上界をあわせると
$$ z(n,n;3,3)=(1+o(1))\,n^{5/3},\qquad\operatorname{ex}(n,K_{3,3})=\Bigl(\frac12+o(1)\Bigr)n^{5/3} $$
となる（後者は FS13 Theorem 3.18、p. 32）。
未解決の状況．Kővári–Sós–Turán の上界の指数が最良である、すなわち $s\le t$ について $\operatorname{ex}(n,K_{s,t})\ge c\,n^{2-1/s}$ となる定数 $c>0$ があるという予想は、$s=2$、$s=3$、$t>(s-1)!$ の場合に正しいことが知られており、最初の未解決の場合は $K_{4,4}$ である（Zha23 予想 1.4.4、p. 24、系 1.10.8、p. 42）。prop-zp-basic の 3・4 により、$z(n,n;4,4)$ の増え方の指数も分かっていない。正確な値については、無限に多くのパラメータで知られているものの、一般には漸近的な評価しかなく、$z(m,n;2,2)$ でさえ十分には分かっていない（FS13 p. 12）。

例と反例

外す条件	反例	成り立たなくなること
thm-zp-culik の $n\ge(t-1)\binom ms$	$m=n=4$、$s=t=2$	$z=(s-1)n+(t-1)\binom ms$
thm-zp-equality の 2 の $q\ge2$	$n=3$ の $J-I$	射影平面の公理 (iii)
thm-zp-culik の $m\ge s$	$m=n=1$、$s=3$、$t=2$	$z=(s-1)n+(t-1)\binom ms$

反例の確かめ

1 行目：$n=4< \binom42=6$ である。prop-zp-small により $z(4,4;2,2)=9$ だが、式の右辺は $4+6=10$ である。prf-zp-culik の構成は 6 本の列を要し、4 本では作れない。
2 行目：$J-I$ の 3 本の列はそれぞれ 2 個の点（行）をもつ。4 個の点がないので公理 (iii) は成り立たない。それでも 1 の個数 $6$ は上界 $\frac32(1+3)=6$ に等しく、thm-zp-equality の 1 は成り立つ（$q=1$）。
3 行目：$1\times1$ の行列では $3$ 個の行を選べないので $z(1,1;3,2)=1$ だが、右辺は $2\cdot1+\binom13=2$ である。構成で使う「$1$ を $s-1$ 個もつ列」が作れない。

長方形の場合の Reiman の上界

$m=3$、$n=7$ では thm-zp-reiman の上界は $\frac12(7+\sqrt{49+168})=\frac12(7+\sqrt{217})\approx10.87$ で、$z(3,7;2,2)\le10$ である。一方 $n=7\ge\binom32$ なので cor-zp-culik-22 により $z(3,7;2,2)=7+3=10$ であり、上界の整数部分が正確な値になる。

補足

名前：Zarankiewicz の名は、完全二部グラフ $K_{m,n}$ の交差数についての予想（Zarankiewicz の交差数予想）にも付いているが、この記事の問題とは別のものである（FS13 p. 24 の脚注）。
起源と経緯：FS13 p. 17 によれば、この問題は位相幾何の問い（平面グラフについての Kuratowski の定理）から生まれた。T. Kővári・V. T. Sós・P. Turán の 1954 年の論文が一般の上界を与え（Kővári–Sós–Turánの定理）、Čulík（1956 年）・Reiman（1958 年）・Brown（1966 年）・Füredi（1996 年）らの仕事が続いた（FS13 pp. 24–38）。
グラフの極値数との違い：$\operatorname{ex}(n,K_{s,t})$ は頂点の分け方を決めない問題で、$z(m,n;s,t)$ は二部分割と向きを決めた問題である。$K_{2,2}$ では $\operatorname{ex}(n,K_{2,2})=\bigl(\frac12+o(1)\bigr)n^{3/2}$（Kővári–Sós–Turánの定理の定理「$K_{2,t}$ の極値数の大きさ」）に対し、$z(n,n;2,2)=(1+o(1))n^{3/2}$ である（prop-zp-basic の 3 と thm-zp-reiman）。