For a positive real number , the -norm of a graph is the sum of the -th powers of all vertex degrees. We study the maximum -norm of -free graphs on vertices, focusing on the case where is a bipartite graph. It is natural to conjecture that for every bipartite graph , there exists a threshold such that for , the order of is governed by pseudorandom constructions, while for , it is governed by star-like constructions. We determine the exact value of , under a mild assumption on the growth rate of . Our results extend to -uniform hypergraphs as well.
We also prove a general upper bound that is tight up to a factor for when .
We conjecture that this 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.