7
$\begingroup$

Problem. Let $T,H$ be fixed graphs with $H$ being a tree, not isomorphic to a subgraph of $T$. Let $ex(n,T,H)$ be the maximal number of copies of $T$ in an $H$-free graph on $n$ vertices. Is it always true that $ex(n,T,H)=\Theta(n^k)$ for $k=k(T,H)\in\mathbb N$?

(The problem was posed on 13.10.2016 by Clara Shikhelman. The promised prize for solution is "a bottle of wine in Tel-Aviv", see page 20 of Volume 1 of the Lviv Scottish Book).

$\endgroup$
7
  • 1
    $\begingroup$ If $H$ is a subgraph of $T$, then $ex(n, T, H) = 0$ for all $n$, which is not $\Theta(n^k)$ for any $k$. $\endgroup$ Sep 30, 2017 at 10:22
  • $\begingroup$ N.B.: $H$ is supposed to be a tree, otherwise it is indeed well known. $\endgroup$
    – Clara Sh
    Sep 30, 2017 at 13:12
  • $\begingroup$ The questions posted by this account are indeed interesting, but it seems like sometimes they are missing key assumptions, because the person posting the question to MO is not the same as the one who originally thought of the question. I wonder if there is a better method for publicizing these questions. $\endgroup$ Sep 30, 2017 at 15:03
  • 1
    $\begingroup$ @SamHopkins Concerning omitted assumptions, rewriting the problem to MathOverFlow, I give a link to the scan of the page where the original problem is written. Sometimes I add the necessary definitions (when I understand the problem). Of course, posting a problem on MathOverFlow is much more responsible comparing to writing it in the Lviv Scottish Book where it remains basically unnoticed. After posting the problem to MathOverFlow I communicate with the authors of the problem requiring to react and comment to the answers. And it eventually works. $\endgroup$ Sep 30, 2017 at 19:43
  • 1
    $\begingroup$ Replacing by $\mathbb N\cup\{0\}$ does not help, since $1\neq\Omega(0)$; you need $-\infty$ instead of $0$... $\endgroup$ Oct 2, 2017 at 8:57

1 Answer 1

7
$\begingroup$

This was an answer to a previous version of the question, when $H$ was not claimed to be a tree.

It is well-known that a maximal number of edges in a $C_4$-free graph is $\Theta(n^{3/2})$ (since every pair of vertices is connected by at most one path of length 2, so the average square of a vertex degree is at most $\Theta(n)$; this is reached, e.g., by the incidence graph of a projective plane). Thus the conjecture fails for $H=C_4$, $T=K_2$.

$\endgroup$
1
  • $\begingroup$ The author of the problem informed me that an additional condition (that $H$ is a tree) should be added. So, your counterexample does not work for this more special case. $\endgroup$ Oct 1, 2017 at 17:49

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.