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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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}$.

Improve this answer
$\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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .