1
$\begingroup$

I know that it must be a simple consequence of the Kővári–Sós–Turán (and Erdős–Stone) theorem, but I am struggling to formulate a proof: Let $H$ be a fixed-size $r$-chromatic graph. Then there exists $\varepsilon = \varepsilon(H)$ s.t. if $G$ is an $n$-vertex graph that contains $\geq n^{r-\varepsilon}$ copies of $K_r$, it must also contain a (not necessarily induced) copy of $H$.

Thanks in advance.

Improve this question
$\endgroup$
3
  • $\begingroup$ I guess by copy of $H$ you mean a (not necessarily induced) subgraph? Otherwise, $K_n$ is a counterexample since it does not contain a copy of any $H$ which is not complete. $\endgroup$
    – Tony Huynh
    Commented Jun 14, 2023 at 16:08
  • $\begingroup$ indeed, not necessarily induced $\endgroup$
    – Yevgeny Levanzov
    Commented Jun 14, 2023 at 16:16
  • $\begingroup$ I'm not sure which of these will be helpful to you, but I might start by looking at Theorem 1 in "Graphs with many r-cliques have large complete r-partite subgraphs" by Nikiforov, Lemma 2.1 and Theorem 2.2 in "Hypergraph Turan Problems" by Keevash, and this question together with the answers and comments mathoverflow.net/questions/234278/… $\endgroup$
    – Louis D
    Commented Jun 14, 2023 at 17:21

1 Answer 1

Reset to default
3
$\begingroup$

This follows from Proposition 2.1 of the paper Many $T$ copies in $H$-free graphs by Alon and Shikhelman.

Theorem (Alon and Shikelman) Let $T$ be a fixed graph with $t$ vertices. Then $ex(n,T,H)=\Omega(n^t)$ if and only if $H$ is not a subgraph of a blow-up of $T$. Otherwise, $ex(n,T,H) \le n^{t-\varepsilon(T,H)}$ for some $\varepsilon(T,H) > 0$.

Here, $ex(n,T,H)$ is the maximum number of copies of $T$ in an $n$-vertex $H$-free graph.

To derive your result, we apply Alon-Shikelman with $T=K_r$ and $H$ a fixed $r$-chromatic graph. Thus, $H$ is a subgraph of a blow-up of $K_r$. So, we may choose $\varepsilon(H)$ to be any positive constant less than $\varepsilon(K_r, H)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is not quite right: the fact that $G$ has $n^{r-\varepsilon}$ copies of $K_r$ does not imply that at most $O(n^\varepsilon)$ $r$-subsets are not cliques, as the $-\varepsilon$ is in the exponent, thus $n^{r-\varepsilon} + x = \Theta(n^r)$ gives $x \approx n^{r-\varepsilon} \cdot (n^\varepsilon - 1)$ $r$-subsets which are not cliques. $\endgroup$
    – Yevgeny Levanzov
    Commented Jun 15, 2023 at 9:32
  • $\begingroup$ You're right. I edited the answer. It follows from a result of Alon and Shikhelman. $\endgroup$
    – Tony Huynh
    Commented Jun 15, 2023 at 11:17
  • $\begingroup$ Indeed, thanks! $\endgroup$
    – Yevgeny Levanzov
    Commented Jun 15, 2023 at 12:03

You must log in to answer this question.

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