0
$\begingroup$

I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices and no $K_{s,t}$ subgraph. However, I was unable to find anything about the tripartite equivalent. Is anything known about the number of edges in an $n$ vertex graph that guarantee $K_{s,t,u}$ as a subgraph? Could someone suggest a reference?

For bipartite graphs, the number of edges that guarantee $K_{s,t}$ is of order $n^{2 - \frac{1}{\min(s,t)}}$. Is there a similar bound for tripartite graphs where the growth rate is determined by the size of the graph?

$\endgroup$

1 Answer 1

4
$\begingroup$

The Erdos-Stone theorem is the reference you are looking for.

For every tripartite graph $G$, the number of edges in an $n$-vertex graph that guarantees $G$ as a subgraph is $n^2/4 + o(n^2)$. It is easy to see that $n^2/4$ is a lower bound (for $n$ even), since the complete bipartite graph does not contain $G$ as a subgraph.

By a result of Chvatal and Szemeredi, for the complete tripartite graph $G=K_3(t)$, which has $t$ vertices in each part, the upper bound can be written as $n^2/4 + n^{2-1/500t}$.

$\endgroup$
3
  • $\begingroup$ For bipartite graphs, the number of edges that guarantee $K_{s,t}$ is of order $n^{2 - \frac{1}{\min(s,t)}}$. Is there a similar bound for tripartite graphs where the growth rate is determined by the size of the graph? $\endgroup$
    – Halbort
    Commented Aug 9, 2015 at 3:29
  • $\begingroup$ I realize my question may be misleading, so I am adding the previous comment to it. $\endgroup$
    – Halbort
    Commented Aug 9, 2015 at 3:29
  • $\begingroup$ I have added a direct reference to a more precise upper bound, which is also mentioned at the Wikipedia page. $\endgroup$
    – Jan Kyncl
    Commented Aug 9, 2015 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.