On Zarankiewicz’s Problem for Intersection Hypergraphs of Geometric Objects

The proof is by induction on $d$. The base case $d=2$ amounts to bounding the number of edges in a $K_{2t,2gt}$-free bipartite intersection graph of a multiset $A$ of horizontal segments in ${ℝ}^2$ and a multiset $B$ of vertical segments in ${ℝ}^2$. Indeed, each “facet intersection” in the plane is either an intersection between a horizontal edge of a rectangle in $A$ with a vertical edge of a rectangle in $B$, or vice versa. We can bound the number of facet intersections of the first type by $|E(G_{A^{\prime },B^{\prime }})|$, where $A^{\prime }$ is the multiset of horizontal edges of rectangles in $A$ and $B^{\prime }$ is the multiset of vertical edges of rectangles in $B$. Note that this intersection graph is $K_{2t,2gt}$-free, as otherwise, $G_{A,B}$ would contain $K_{t,gt}$. The second type can be handled similarly. Hence, Proposition 7 yields a bound of $O(g{t}^{2}n+tm)$ in this setting, which proves the induction basis.

In the induction step, we assume that for $(d-1)$-dimensional boxes, the number of facet intersections is bounded by

We bound the number of facet intersections between $x\in A$ and $y\in B$, such that the intersecting facets are othogonal to the $(d-1)$’th and the $d$’th axis, respectively. A bound on the total number of facet intersections clearly follows by multiplying with $d^2$. In the rest of the proof, we call such special intersections “good facet intersections”, or just “intersections” for brevity. We make sure that in the dimension reductions in the induction process presented below, every time the first coordinate is the one that is removed, and thus, the good facet intersections are not affected.

We use the following auxiliary notion. Let $I_d(n,m)$ be the maximum number of good facet intersections between multisets $A,B$ of axis-parallel boxes inside a “vertical strip” of ${ℝ}^d$, where:

1. 1.

   Each box in $A,B$ has either half of its vertices or all of its vertices in $𝒰$;

2. 2.

   The total number of vertices of boxes in $A$ (resp., boxes in $B$) inside $𝒰$ is $n\cdot 2^{d-1}$ (resp., $m\cdot 2^{d-1}$);

3. 3.

   The bipartite intersection graph of $A,B$ is $K_{t,gt}$-free.

We shall prove that

This clearly implies the assertion of the proposition, as by considering a vertical strip $𝒰$ that fully contains all boxes in $A$ and $B$ (where $|A|=n$ and $|B|=m$), we get that the number of good facet intersections between $A$ and $B$ is at most $I_d(2n,2m)$. (Note that we neglect factors of $O_d(1)$).

Let $A,B$ be multisets of boxes that satisfy assumptions (1)–(3) with respect to a strip $𝒰\subset {ℝ}^d$. We divide $𝒰$ into two vertical sub-strips and , such that each sub-strip contains $n\cdot 2^{d-2}$ vertices of boxes in $A$. For $i=1,2$, we denote by $A_i$ (resp., $B_i$) the boxes in $A$ (resp., $B$) that have at least one vertex in ${\sigma }_i$, and by $A_i^{\prime }$ (resp., $B_i^{\prime }$) the boxes in $A$ (resp., $B$) that intersect ${\sigma }_i$ but do not have vertices in it. Note that $A_1^{\prime }\subset A_2,A_2^{\prime }\subset A_1$, and similarly for $B$. We also denote the number of vertices of boxes in $B$ contained in ${\sigma }_i$ by $2^{d-1}\cdot m_i$.

The number of good facet intersections in $𝒰$ between boxes in $A$ and boxes in $B$ is at most

where $I(X,Y)$ denotes the number of good facet intersections between an element of $X$ and an element of $Y$.

Indeed, $I(A_1,B_1)$ (resp., $I(A_2,B_2)$) counts intersections between pairs of boxes that have at least one vertex in ${\sigma }_1$ (resp., ${\sigma }_2$). $I(A_1,B_1^{\prime })+I(A_2^{\prime },B_2)$ upper bounds the number of intersections between a box in $A$ that has a vertex in ${\sigma }_1$ and a box in $B$ that has a vertex in ${\sigma }_2$. $I(A_2,B_2^{\prime })+I(A_1^{\prime },B_1)$ upper bounds the number of intersections between a box in $A$ that has a vertex in ${\sigma }_2$ and a box in $B$ that has a vertex in ${\sigma }_1$.

By the definitions, we have $I(A_1,B_1)\le I_d(\frac{n}{2},m_1)$ (where ${\sigma }_1$ is taken as the vertical strip instead of $𝒰$). Similarly, $I(A_2,B_2)\le I_d(\frac{n}{2},m_2)$.

To handle the other types of intersections, we observe that a box in $A_1$ intersects a box in $B_1^{\prime }$ if and only if their projections on the hyperplane $\mathscr{H}=\{x\in {ℝ}^d:x_1=u^{\prime }\}$ (which are $(d-1)$-dimenstional boxes) intersect. Let ${\overline{A}}_1$ and ${\overline{B}}_1^{\prime }$ denote the corresponding families of projections. We have $|{\overline{A}}_1|=|A_1|=\frac{n}{2}$ and $|{\overline{B}}_1^{\prime }|=|B_1^{\prime }|\le m_2$. The multisets ${\overline{A}}_1$ and ${\overline{B}}_1^{\prime }$ are multisets of axis-parallel boxes in ${ℝ}^{d-1}$ whose bipartite intersection graph is $K_{t,gt}$-free. Hence, by the induction hypothesis we have

Applying the same argument to $I(A_2^{\prime },B_2),I(A_1^{\prime },B_1)$ and $I(A_2,B_2^{\prime })$, we get

Combining this with the bounds on $I(A_1,B_1)$ and $I(A_2,B_2)$ and substituting to (1), we obtain the recursive formula

which solves to

This completes the proof. $◀$

Let $A,B$ be multisets of axis-parallel boxes in ${ℝ}^d$ that satisfy the assumptions of the theorem. As written above, the intersections between $A$ and $B$ can be divided into vertex containment intersections and facet intersections.

To bound the number of vertex containment intersections, we apply Proposition 5, with $ϵ=\frac{1}{2}$. Specifically, we use Proposition 5(1) to bound the number of intersections in which a vertex of $a\in A$ is contained in a box $b\in B$. Furthermore, we use Proposition 5(2) with the roles of $n$ and $m$ reversed to bound the number of intersections in which a vertex of $b\in B$ is contained in a box $a\in A$. We get that the number of vertex containment intersections is at most

By Proposition 6, the number of facet intersections is at most

Note that for a large $n$, we have ${(\log n)}^{d-2}=o({(\frac{\log n}{\log \log n})}^{d-1.5})$, and hence, the number of facet intersections is dominated by the number of vertex containment intersections.

Finally, since $m=\mathrm{poly}(\mathrm{n})$, the terms $tm{(\frac{\log n}{\log \log n})}^{d-1.5}$ and $g{t}^{2}n{(\frac{\log m}{\log \log m})}^{d-1.5}$ are dominated by the two other terms. Therefore, we have

as asserted. This completes the proof. $◀$

Let $A_1=A,A_2=B,A_3=C$. Let $AB$ be the following multiset of axis-parallel boxes: $AB=\{a\cap b:a\in A,b\in B,a\cap b\ne \mathrm{\varnothing }\}$. (Note that the intersection of two axis-parallel boxes is indeed an axis-parallel box). Let $G$ be the bipartite intersection graph of the families $C$ and $AB$. It is clear that $|E(G)|=|ℰ(H)|$, since there is a clear one-to-one correspondence between edges of $G$ and hyperedges of $H$.

We claim that for a sufficiently large constant $M$, the graph $G$ is $K_{t,Mtn{f}_{d,t}(n)}$-free. Indeed, assume to the contrary that $G$ contains a copy of $K_{t,Mtn{f}_{d,t}(n)}$, for a “large” $M$. This means that there exist $t$ boxes $c_1,c_2,\mathrm{\dots },c_t\in C$ which all have a non-empty intersection with certain $Mtn{f}_{d,t}(n)$ axis-parallel boxes of the form $a_i\cap b_i$, with $a_i\in A$, $b_i\in B$. Denote by $A^{\prime }$ the set of all $a_i\in A$ that participate in such intersections, and by $B^{\prime }$ the set of all $b_i\in B$ that participate in such intersections. Let $G^{\prime }$ be the bipartite intersection graph of $A^{\prime },B^{\prime }$. We have $|E(G^{\prime })|\ge Mtn{f}_{d,t}(n)$, and hence, by Theorem 3 (applied with $m=n$ and $g=1$), it contains a $K_{t,t}$ (using the assumption that $M$ is sufficiently large). This means that there exist $a_1,a_2,\mathrm{\dots },a_t\in A$ and $b_1,b_2,\mathrm{\dots },b_t\in B$ such that for all $1\le i,j\le t$, we have $a_i\cap b_j\ne \mathrm{\varnothing }$, and both $a_i$ and $b_j$ have a non-empty intersection with each of $c_1,\mathrm{\dots },c_t$ (since they participate in pairs whose intersection with each of $c_1,\mathrm{\dots },c_t$ is non-empty). As any three pairwise intersecting axis-parallel boxes have a non-empty intersection, this implies that $a_i\cap b_j\cap c_k\ne \mathrm{\varnothing }$ for all $1\le i,j,k\le t$, and consequently, $H$ contains a $K_{t,t,t}$, a contradiction.

We have thus concluded that $G$ is $K_{t,Mtn{f}_{d,t}(n)}$ free, for a sufficiently large constant $M$. By Theorem 3, applied with $n$, $m=n^2$, and $g=Mn{f}_{d,t}(n)$, this implies that

This completes the proof. $◀$

Note that in this proof, we used the fact that axis-parallel boxes in ${ℝ}^d$ have Helly number 2, namely, that any pairwise intersecting family of axis-parallel boxes has a non-empty intersection. Without this property, the existence of $K_{t,t}$ in $G^{\prime }$ does not necessarily imply the existence of $K_{t,t,t}$ in $H$.

The proof for a general $r$ is an inductive process, in which at the $\mathrm{\ell }$’th step, one considers an auxiliary bipartite intersection graph of boxes, whose vertex sets are the multiset $A_1{A}_2\mathrm{\dots }{A}_{\mathrm{\ell }+1}=\{(a_1\cap \mathrm{\dots }\cap a_{\mathrm{\ell }+1}):\forall i,a_i\in A_i,{\cap }_{i=1}^{\mathrm{\ell }+1}{a}_i\ne \mathrm{\varnothing }\}$, where the multiplicity of each element is the number of $(a_1,\mathrm{\dots },a_{\mathrm{\ell }+1})$ tuples that lead to it, and $A_{\mathrm{\ell }+2}$. At each step, Theorem 3 is applied once again, and the fact that axis-parallel boxes have Helly number 2 is deployed once again. As this part of the proof is a bit more cumbersome and is not needed for the proof of Theorem 1 presented below, we provide it in the full version of the paper [4].

Let $T_G(n_1,\mathrm{\dots },n_r)$ be the maximum number of hyperedges in a $K_{t,\mathrm{\dots },t}^r$-free $r$-partite intersection hypergraph $H$ of $r$ families $A_1,\mathrm{\dots },A_r$ of axis-parallel boxes in ${ℝ}^d$, where $|A_i|=n_i$, and the constraints graph of $r$-tuple $A_1,\mathrm{\dots },A_r$ is $G$. Denote $T_G(n)=T_G(n,\mathrm{\dots },n)$. In order to prove the theorem, it is clearly sufficient to prove that for any constraint graph $G$, we have $T_G(n)\le O(t{n}^{r-1}{f}_{d,t}(n))$. We prove this claim by induction on $|E(G)|$.

If $E(G)=\mathrm{\varnothing }$, then for all $i\ne j$, any $a_i\in A_i$ intersects any $a_j\in A_j$. Since $H$ is $K_{t,\mathrm{\dots },t}^r$-free, this implies and we are done.

In the induction step, we assume that we have already proved the claim for any constraints graph with a smaller number of edges, and we now consider a constraints graph $G$. We consider three cases:

• $\mathrm{■}$

  Case A: $G$ contains two non-adjacent edges;

• $\mathrm{■}$

  Case B: $G$ is a triangle;

• $\mathrm{■}$

  Case C: $G$ is a star.

Clearly, any graph $G$ belongs to one of the three cases.

Say these two non-adjacent edges are $(1,2)$ and $(3,4)$. Our goal now is to “remove” the edge $(1,2)$ (and later, also the edge $(3,4)$) from $G$, by partitioning the intersection graph of $A_1$ and $A_2$ into bicliques. To this end, we use Lemma 11 with a large constant $b$ to partition the entire hypergraph into smaller hypergraphs, induced by a partition of the bipartite intersection of $A_1$ and $A_2$ to “full” bicliques and “partial” bicliques. We obtain the recursion:

where the right term comes from applying the induction hypothesis on the hypergraphs induced by full bicliques, whose constraints graph is $G\setminus \{(1,2)\}$, and the left term comes from the partial bicliques.

Now, to bound $T_G(\frac{n}{b},\frac{n}{b},n,\mathrm{\dots },n)$, we do the same with the sets $A_3,A_4$ and obtain

Combining (2) and (3) together, we get

To bound the left term in the right hand side, we partition the hypergraph into $b^{r-4}$ hypergraphs which $r$ sides of size $\frac{n}{b}$ by partitioning each of the sets $A_5,\mathrm{\dots },A_r$ arbitrarily into $b$ parts, each of size $\frac{n}{b}$. We obtain

The recursion (5) solves to $T_G(n)=O(t{n}^{r-1}{f}_{d,t}(n))$, and we are done.

Say $E(G)=\{(1,2),(2,3),(1,3)\}$. In this case, we first split $A_1$ and $A_2$ by Lemma 11, then we split $A_2$ and $A_3$ and then we split $A_1$ and $A_3$.

Using the induction hypothesis, by splitting $A_1,A_2$ we obtain

By splitting $A_2,A_3$, we get

and by splitting $A_1,A_3$ we have

Combining (6)-(8), we obtain

and by partitioning each of $A_4,\mathrm{\dots },A_r$ arbitrarily into $b^2$ equal parts, we get

As above, this recursion solves to $T_G(n)=O(t{n}^{r-1}{f}_{d,t}(n))$.

Say $G$ is a star centered at $A_r$. In this case we don’t apply the induction hypothesis. Instead, we apply Theorem 3 (only once, in contrast to the argument in Section 2.2.1).

Assume on the contrary that $T_G(n)>Ct{n}^{r-1}{f}_{d,t}(n)$ for some large constant $C$. Consider the intersection graph between the multiset $A_1{A}_2\mathrm{\dots }{A}_{r-1}=\{a_1\cap \mathrm{\dots }\cap a_{r-1}:\forall i,a_i\in A_i,{\cap }_{i=1}^{r-1}{a}_i\ne \mathrm{\varnothing }\}$ and the family $A_r$. Since the number of edges in this graph is at least $\mathrm{\Omega }(t{n}^{r-1}{f}_{d,t}(n))$, by Theorem 3 (with the parameters $n,m=n^{r-1}$ and $g=n^{r-2}$), this intersection graph contains $K_{gt,t}$.