On the approximate shape of degree sequences that are not potentially $H$-graphic

Abstract

A sequence of nonnegative integers $\pi$ is {\it graphic} if it is the degree sequence of some graph $G$. In this case we say that $G$ is a \textit{realization} of $\pi$, and we write $\pi =\pi (G)$. A graphic sequence $\pi$ is {\it potentially $H$-graphic} if there is a realization of $\pi$ that contains $H$ as a subgraph. Given nonincreasing graphic sequences ${\pi }_1=(d_1,\dots ,d_n)$ and ${\pi }_2=(s_1,\dots ,s_n)$, we say that ${\pi }_1$ {\it majorizes} ${\pi }_2$ if $d_i\ge s_i$ for all $i$, $1\le i\le n$. In 1970, Erdős showed that for any $K_{r+1}$-free graph $H$, there exists an $r$-partite graph $G$ such that $\pi (G)$ majorizes $\pi (H)$. In 2005, Pikhurko and Taraz generalized this notion and showed that for any graph $F$ with chromatic number $r+1$, the degree sequence of an $F$-free graph is, in an appropriate sense, nearly majorized by the degree sequence of an $r$-partite graph. In this paper, we give similar results for degree sequences that are not potentially $H$-graphic. In particular, there is a graphic sequence ${\pi }^{\ast }(H)$ such that if $\pi$ is a graphic sequence that is not potentially $H$-graphic, then $\pi$ is close to being majorized by ${\pi }^{\ast }(H)$. Similar to the role played by complete multipartite graphs in the traditional extremal setting, the sequence ${\pi }^{\ast }(H)$ asymptotically gives the maximum possible sum of a graphic sequence $\pi$ that is not potentially $H$-graphic.

19 pages