Jun Gao (高峻), Phase transition of degenerate Turán problems in p-norms
December 13 Friday @ 4:30 PM - 5:30 PM KST
For a positive real number $p$, the $p$-norm $\|G\|_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, focusing on the case where $F$ is a bipartite graph. It is natural to conjecture 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. We determine the exact value of $p_{F}$, under a mild assumption on the growth rate of $\mathrm{ex}(n,F)$. Our results extend to $r$-uniform hypergraphs as well.
We also prove a general upper bound that is tight up to a $\log n$ factor for $\mathrm{ex}_{p}(n,F)$ when $p = p_{F}$.
We conjecture that this $\log n$ factor is unnecessary and prove this conjecture for several classes of well-studied bipartite graphs, including one-side degree-bounded graphs and families of short even cycles.
This is a joint work with Xizhi Liu, Jie Ma and Oleg Pikhurko.