Supersaturation thresholds for expanded color-critical graphs

Abstract

For a $k$-uniform hypergraph $L$, let $h_L(n,q)$ be the minimum number of copies of $L$ in an $n$-vertex $k$-graph with $\mathrm{ex}(n,L)+q$ edges. Let $t_L(n,q)$ be the minimum number of copies obtained by adding $q$ edges to an extremal $L$-free $k$-graph. A graph is color-critical if deleting a suitable edge decreases its chromatic number. Let ${\mathcal{K}}_k(F)$ be the expanded graph obtained by adding $k-2$ new vertices to each edge of $F$, with disjoint sets of new vertices for distinct edges. Mubayi proved that, for every clique $K_r$ with $r\ge 4$ and fixed $q>0$, $h_{{\mathcal{K}}_3(K_r)}(n,q)\ge q{t}_{{\mathcal{K}}_3(K_r)}(n,1)$ for every sufficiently large $n$. Pikhurko and Yilma later proved that, for every color-critical graph $F$, there is a constant ${\epsilon }_F>0$ such that $h_F(n,q)=t_F(n,q)$ for every sufficiently large $n$ and $1\le q\le {\epsilon }_{F}n$. We extend this equality to expanded color-critical graphs. Let $d>k\ge 3$. For every color-critical graph $F$ with $\chi (F)=d+1$, there is a constant $\epsilon >0$ such that $h_{{\mathcal{K}}_k(F)}(n,q)=t_{{\mathcal{K}}_k(F)}(n,q)$ for every sufficiently large $n$ and $1\le q\le \epsilon n^{k-1}$. Let $q_L(n)$ be the largest integer $q$ such that $h_L(n,s)=t_L(n,s)$ for every integer $1\le s\le q$. We give a sufficient condition for $q_L(n)={\Theta }_L(n^{k-1})$ and an explicit family satisfying it. We also give a different sufficient condition under which $q_L(n)={\Omega }_L(n^{k-1/2})$ and an explicit family satisfying it. \noindent \emph{Keywords.} Supersaturation; extremal graph; color-critical graph; chromatic number; expanded graph; hypergraph.