Tag: JunGao

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, 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.

We prove that for $n>k\ge 3$, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai.

This is joint work with Jie Ma.