Unified approach to the generalized Turán problem and supersaturation

NEW

Problem: Reconstructed statement: for fixed integers $k>\ell\ge2$, where $P_r$ is the path on $r$ vertices and

the conjecture asserts that, asymptotically in $n$, this minimum is achieved by either a quasi-clique or a quasi-star. Here $\mathcal N(H,G)$ denotes the number of unlabelled copies of $H$ in $G$.

This is the natural reading from the paper’s definition of $\operatorname{satex}$ and its definitions of quasi-clique/quasi-star.

Result: The conjecture is false. A counterexample occurs already for $(k,\ell)=(5,4)$.

Let

and let $G_n=K_{a,b}$. Put

For a complete bipartite graph $K_{x,y}$,

and

Hence, since $a=o(n)$,

while

Thus

Now compare with quasi-stars and quasi-cliques.

A quasi-star differs in at most one exceptional vertex from a split graph

For $h=o(n)$,

and

The exceptional vertex contributes only $O(n^4)=o(m_n)$ copies of $P_5$ and $O(n^3)=o(a^2n^2)$ copies of $P_4$. Therefore any quasi-star with at least $m_n$ copies of $P_5$ must have $h\ge(1-o(1))a$, and hence has at least

copies of $P_4$.

A quasi-clique with clique part of size $c$ has at most $\frac12(c+1)_5$ copies of $P_5$. Therefore $m_n\le \frac12(c+1)_5$ implies

It then contains at least

copies of $P_4$, which is $\omega(a^2n^2)$ because $a=n^{2/3+o(1)}$.

Consequently every quasi-star or quasi-clique with at least $m_n$ copies of $P_5$ has at least

copies of $P_4$, while $K_{a,b}$ has only

The ratio is asymptotically at most $2/3$, so the extremum is not asymptotically attained by a quasi-star or quasi-clique.

Thus Conjecture 5.6, under its natural formalization, is false.

Citation: No known published disproof is being invoked. The conjecture and notation are from Gerbner–Nagy–Vizer, “Unified approach to the generalized Turán problem and supersaturation,” arXiv:2008.12093.