On subgraphs of tripartite graphs

Let $K_{t}$ denote the complete graph on $t$ vertices. As a foundation stone of extremal graph theory, Turán’s theorem in 1941 [10] determines the maximum number of edges in graphs of a given order not containing $K_{t}$ as a subgraph (the $t=3$ case was proven by Mantel in 1907 [6]). In 1975 Bollobás, Erdős, and Szemerédi [1] investigated the following Turán-type problem for multipartite graphs.

The $r=t$ case of Problem 1 had been a central topic in Combinatorics until it was finally settled by Haxell and Szabó [4], and Szabó and Tardos [8]. Recently Lo, Treglown, and Zhao [9] solved many $r>t$ cases of the problem, including when $r\equiv-1\pmod{t-1}$ and $r=\Omega(t^{2})$.

For simplicity, let $G_{r}(n)$ denote an (arbitrary) $r$-partite graph with parts of size $n$. Let $K_{r}(s)$ denote the complete $r$-partite graph with parts of size $s$. In particular, $K_{3}(2)$ is known as the Octahedral graph. In the same paper Bollobás, Erdős, and Szemerédi [1] also asked the following question.

Problem 2 is a natural generalization of the well-known Zarankiewicz problem [11], whose symmetric version asks for the largest number of edges in a bipartite graph $G_{2}(n)$ that contains no $K_{2}(s)$ as a subgraph (in other words, $K_{2}(s)$-free).

In [1, Corollary 2.7] the authors stated that $\delta(G)\geq n+2^{-1/2}n^{3/4}$ guarantees a copy of $K_{3}(2)$. This follows from [1, Theorem 2.6], which handles the general case of $K_{3}(s)$ for arbitrary $s$. Unfortunately, there is a miscalculation in the proof of [1, Theorem 2.6] and thus the bound $\delta(G)\geq n+2^{-1/2}n^{3/4}$ is unverified. We follow the approach of [1, Theorem 2.6] and obtain the following result.

In particular, Theorem 3 implies that every $G=G_{3}(n)$ with $\delta(G)\geq n+(1+o(1))n^{11/12}$ contains a copy of $K_{3}(2)$. Using a result of Erdős on hypergraphs [3], we give a different proof of Theorem 3 under a slightly stronger condition $\delta(G)\geq n+(3n)^{1-1/(3s^{2})}$. Thus $c\,n^{11/12}$ is a natural additive term for Problem 2 under typical approaches for extremal problems.

On the other hand, the authors of [1] conjectured that $\delta(G)\geq n+cn^{1/2}$ suffices for Problem 2. Although not explained in [1], they probably thought of Construction 10, a natural construction based on the one for the Zarankiewicz problem. We indeed find many non-isomorphic constructions, Construction 11, with the same minimum degree.

Theorem 3 and Proposition 4 together show that the answer for Problem 2 lies between $n+n^{1/2}$ and $n+n^{11/12}$. The truth may be closer to the lower bound. If this is the case, then verifying it may be hard given the presence of many non-isomorphic constructions.

We know less about the minimum degree of $G_{3}(n)$ that forces a copy of $K_{3}(s)$. Theorem 3 shows that $\delta(G_{3}(n))\geq n+cn^{1-1/(3s^{2})}$ suffices. As shown in Remark 12, if there is a $K_{2}(s)$-free bipartite graph $B=G_{2}(n)$ with $\delta(B)=\Omega(n^{1-1/s})$, then our constructions for Proposition 4 provide a tripartite $K_{3}(s)$-free graph $G=G_{3}(n)$ with $\delta(G)=n+\Omega(n^{1-1/s})$.

In order to prove Theorem 3, we need the following results from [1].

Let $z(n,s)$ denote the largest number of edges in a bipartite $K_{2}(s)$-free graph with $n$ vertices in each part. Kővári, Sós, and Turán [5] gave the following upper bound for $z(n,s)$.¹¹1In [1] the authors instead used the Turán number ex$(2n,K_{2}(s))$, which gives a slightly worse constant here.

We are ready to prove Theorem 3.

We now give another proof of Theorem 3 with slightly larger $\delta(G)$ by a classical result of Erdős on hypergraphs [3]. An $r$-uniform hypergraph or $r$-graph is a hypergraph such that all its edges contain exactly $r$ vertices. Let $K^{r}_{r}(s)$ denote the complete $r$-partite $r$-graph with $s$ vertices in each part, namely, its vertex set consists of disjoint parts $V_{1},\dots,V_{r}$ of size $s$, and edges set consists of all $r$-sets $\{v_{1},\dots,v_{r}\}$ with $v_{i}\in V_{i}$ for all $i$.

In this section we prove Proposition 4 by constructing many tripartite $K_{3}(2)$-free graphs $G_{3}(n)$ with $\delta(G_{3}(n))\geq n+n^{1/2}$.

One main building block is a bipartite $K_{2}(2)$-free graph $G_{0}=G_{2}(n)$ with $\delta(G_{0})\geq\sqrt{n}$. First shown in [7], such a graph exists when $n=q^{2}+q+1$ and a projective plane of order $q$ exists. Indeed, two parts of $V(G)$ correspond to the points and lines of the projective plane and a point is adjacent to a line if and only if the point lies on the line. It is easy to see that such graph contains no $K_{2}(2)$ and is regular with degree $q+1>\sqrt{n}$.

We now provide a family of constructions with the same properties.

If letting $X_{2}=\emptyset=Y_{3}$ in Construction 11, then we obtain Construction 10. Nevertheless, we prefer viewing Constructions 10 and 11 as different constructions because after removing $o(n^{2})$ edges, Construction 11 contains many 5-cycles while Construction 10 does not.