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).

Improve this question
$\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$
    – Mikhail Tikhomirov
    Commented 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
    Commented 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$
    – Sam Hopkins
    Commented 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$
    – Lviv Scottish Book
    Commented 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$
    – Ilya Bogdanov
    Commented Oct 2, 2017 at 8:57

1 Answer 1

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

Improve this answer
$\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$
    – Lviv Scottish Book
    Commented Oct 1, 2017 at 17:49

You must log in to answer this question.

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