Phase transition of degenerate Turán problems in $p$-norms

Abstract

For a positive real number $p$, the $p$-norm ${\Vert G\Vert }_p$ of a graph $G$ is the sum of the $p$-th powers of all vertex degrees. We study the maximum $p$-norm ${\mathrm{ex}}_p(n,F)$ of $F$-free graphs on $n$ vertices. Füredi and Kündgen \cite{FK06} show that for every bipartite graph $F$, there exists a threshold $p_F$ such that for $p<p_F$, the order of ${\mathrm{ex}}_p(n,F)$ is governed by pseudorandom constructions, while for $p>p_F$, it is governed by star-like constructions, assuming a mild assumption on the growth rate of $\mathrm{ex}(n,F)$. The main contribution of our paper is extending this result to hypergraph. Moreover, in the case of graph, our proof differs from that in \cite{FK06}, offering the advantage of producing the correct constant factor when $p>p_F$. When $p=p_F$, Füredi and Kündgen proved a general upper bound on ${\mathrm{ex}}_p(n,F)$, tight up to a $\log n$ factor, and conjectured that this factor is unnecessary. We confirm this conjecture for several well-studied bipartite graphs, including one-side degree-bounded graphs and families of short even cycles.

28 pages, we added a remark at the end of the Introduction