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

A sequence of nonnegative integers pi is graphic if it is the degree sequence of some graph G. In this case we say that G is a realization of pi, andwewrite pi = pi(G). A graphic sequence pi is potentially Hgraphic if there is a realization of pi that contains H as a subgraph. Given nonincreasing graphic sequences pi (1) = (d(1), ..., d(n)) and pi(2) = (s(1), ..., s(n)), we say that pi(1) majorizes pi(2) if d(i) >= s(i) for all i, 1 = i = n. In 1970, Erd. os showed that for any Kr+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*(H) such that if pi is a graphic sequence that is not potentially H-graphic, then pi is close to being majorized by pi*(H). Similar to the role played by complete multipartite graphs in the traditional extremal setting, the sequence pi*(H) asymptotically gives the maximum possible sum of a graphic sequence pi that is not potentially H-graphic.