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$
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}$.

| cite | improve this answer | |
$\endgroup$
  • $\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 Aug 9 '15 at 3:29
  • $\begingroup$ I realize my question may be misleading, so I am adding the previous comment to it. $\endgroup$ – Halbort Aug 9 '15 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 Aug 9 '15 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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