Realization Problems for Graphic and Hypergraphic Sequences

A nonnegative integer sequence $\pi$ is graphic if there is some simple graph $G$ having degree sequence $\pi$. In that case, $G$ is said to realize or be a realization of $\pi$. As there are a number of necessary and sufficient conditions for a sequence to be graphic, considerable attention has been given to the study of when a graphic sequence has a realization with a given property. The typical problems in this area are both inspired by classical results, and have also been recently inspired by the study of complex networks from various application areas.

In this talk, we will discuss a number of results on realizations of graphic sequences. These include new extremal results for potentially $H$-graphic sequences, which are graphic sequences with at least one realization that contains a fixed subgraph $H$. Additionally, we will discuss some of the challenges in studying the degree sequences of $k$-uniform hypergraphs, and present both results and a number of open problems. This work is joint with a number of coauthors.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.