Paper detail

On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic

A sequence of nonnegative integers π=(d_1,d_2,...,d_n) is graphic if there is a (simple) graph G with degree sequence π. In this case, G is said to realize or be a realization of π. Degree sequence results in the literature generally fall into two classes: forcible problems, in which all realizations of a graphic sequence must have a given property, and potential problems, in which at least one realization of πmust have the given property. Given a graph H, a graphic sequence πis potentially H-graphic if there is some realization of πthat contains H as a subgraph. In 1991, Erdős, Jacobson and Lehel posed the following question: Determine the minimum integer σ(H,n) such that every n-term graphic sequence with sum at least σ(H,n) is potentially H-graphic. As the sum of the terms of πis twice the number of edges in any realization of π, the Erdős-Jacobson-Lehel problem can be viewed as a potential degree sequence relaxation of the (forcible) Turán problem, wherein one wishes to determine the maximum number of edges in a graph that contains no copy of H. While the exact value of σ(H,n) has been determined for a number of specific classes of graphs (including cliques, cycles, complete bigraphs and others), very little is known about the parameter for arbitrary H. In this paper, we determine σ(H,n) asymptotically for all H, thereby providing an Erdős-Stone-Simonovits-type theorem for the Erdős-Jacobson-Lehel problem.