ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST

Realization Problems for Graphic and Hypergraphic Sequences

Michael Ferrara
Department of Mathematics, University of Colorado Denver

Tuesday, May 12, 2015 15:00-16:00,
Building 227, Room A302
Tuesday, May 12, 2015 13:00-14:00,


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

Contact: J. Shook

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

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2015-05-12.