1
$\begingroup$

I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t.

The motivation is that we now $ex_2(n,K_{t,t})=O(n^{2-\frac{1}{t}})$ for complete bipartite graph with parts of size t and t. And $ex_2(n,K_{t,t,t})=O(n^2)$. Therefore there should be a bound of $ex_2(n,K_{1,t,t})$ between $n^{2-\frac{1}{t}}$ and $n^2$. I wonder if there is some result in this area.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ By the Erdős–Stone theorem, the answer is the same as that for $K_{t,t,t}$, since both graphs have chromatic number $3$. That is, the Turan number for $K_{1,t,t}$ is $(1/2 + o(1))\binom{n}{2}$. $\endgroup$
    – Tony Huynh
    Commented Mar 22, 2016 at 17:54
  • 1
    $\begingroup$ To add to Tony's comment, the Erdős–Stone Theorem gives the correct asymptotics for any non-bipartite graph. Its possible, however, that one could obtain an improvement on the lower order terms of the asymptotics for $K_{1,t,t}$. $\endgroup$
    – Jon Noel
    Commented Mar 24, 2016 at 8:48

2 Answers 2

Reset to default
2
$\begingroup$

Adding something further: the following is a theorem of Simonovits, which more or less everyone seems to have forgotten exists (buried in some conference proceedings, I think from the mid-80s) that more or less reduces the general problem to the (very interesting) bipartite case.

Given any graph $H$, the decomposition family of $H$ is the collection of bipartite graphs which arise as subgraphs of $H$ induced by any two colour classes in any proper $\chi(H)$-colouring of $H$.

Let the extremal number of the decomposition family be $f_H(n)$. If $f_H(n)$ grows superlinearly, then the difference between the extremal number of $H$ and of $K_{\chi(H)}$ is $\Theta(f_H(n))$.

In fact, it's not so hard to extend this to allow $f_H(n)$ to grow linearly; Simonovits didn't do this (or at least, if he did it is even more buried), and as far as I know this is not in the literature.

In any case, this gives that the extremal number of $K_{1,t,t}$ is $n^2/2+O(n)$. It's maybe a good exercise to follow LouisD's suggestion to prove the exact value; it works with no particular difficulty following the method in David Conlon's notes. The extremal graphs are obtained from the complete balanced bipartite graph on $n$ vertices by adding edge-maximum graphs with no vertex of degree $t$ into each of the partition classes, and you can even prove that all extremal graphs have this structure.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for pointing this out! I've always wondered if determining the exact value for all bipartite graphs would give the exact result for all graphs, and I certainly wasn't aware of this result (any more info on where I could find it?). I often hear things like "Erdos-Stone gives us the correct asymptotics for non-bipartite graphs," but I think it would be better to say something like "Erdos-Stone gives the correct asymptotics for all graphs, but says nothing about the lower order terms for any graph. It just so happens that for bipartite graphs the lower order terms are all there is." $\endgroup$
    – Louis D
    Commented Aug 5, 2016 at 22:09
  • $\begingroup$ I forgot the exact reference, I'm afraid - I just remember it being impossible to find outside Oberwolfach library. As a next best, combinatorics.org/ojs/index.php/eljc/article/view/v17i1r21 does the same for the Andrasfai-Erdos-Sos theorem. You can easily get Simonovits' theorem from this by deleting low-degree vertices until it applies. But the method here isn't good for getting precise answers like K_{1,t,t}. $\endgroup$
    – user36212
    Commented Aug 7, 2016 at 21:26
0
$\begingroup$

Now to add to Jon's comment. Just take the case $t=2$ and suppose for simplicity that $n$ is divisible by 4. I'm guessing that $ex_2(n,K_{1,2,2})=\frac{n^2}{4}+\frac{n}{2}$ by taking a complete balanced bipartite graph and adding a matching of size $\frac{n}{4}$ inside each part. To show this, I would start by showing that the graph must be "close" to a complete bipartite graph (there's a carefully worked out example for odd cycles in David Conlon's notes here https://www.dpmms.cam.ac.uk/~dc340/EGT12.pdf and this should go similarly). Next it should be possible to show that having a path on 3 vertices inside either part would be bad (for maximizing the number of edges) as it would cause us to have to delete many edges going across the partition to avoid having a $K_{1,2,2}$ (if you're feeling inspired to try to work out the details, see https://www.dpmms.cam.ac.uk/~dc340/EGT13.pdf for the second part the example for odd cycles).

Improve this answer
$\endgroup$

You must log in to answer this question.

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