Monday, September 25 2017

11:00am - 12:15am

11:00am - 12:15am

Department Seminar

PhD Research Proposal: Nathan Graber

Extremal Problems for Degree Sequences of Graphs and Hypergraphs

Extremal Problems for Degree Sequences of Graphs and Hypergraphs

Given a graph G and a vertex v in V(G), let d(v) denote the degree of v. The degree sequence of a graph G with vertex set {v_1,\dots,v_n\} is the sequence (d_1,...d_n) where d_i=d(v_i) for 1<= i <= n. A non-increasing sequence \pi = (d_1,\dots,d_n) is graphic if there exists some simple graph G such that \pi is the degree sequence of G. In this case, we say that G is a realization of \pi.

A graphic sequence may have many nonisomorphic realizations, and in this proposal, we are generally concerned with exploring the family of realizations of a given graphic sequence. For a graph property P, a sequence \pi is potentially P-graphic if there is at least one realization of \pi with property P.

Given a graph H, we will focus on potentially H-graphic sequences, which are sequences in which at least one realization contains H as a subgraph. We more specifically focus on the potential number, which is the minimum degree sum necessary for a graphic sequence to be potentially H-graphic. We will discuss general asymptotic results for the potential number from Ferrara, Lesaulnier, Moffatt and Wenger. We will also discuss several recent stability results before proposing to study several open stability questions. Finally, we consider the potential number problem in the hypergraph space. Specifically, we will review the relatively few results known on the degree sequences of hypergraphs, and proposes tools and techniques that may be useful in exploring the problem.

A graphic sequence may have many nonisomorphic realizations, and in this proposal, we are generally concerned with exploring the family of realizations of a given graphic sequence. For a graph property P, a sequence \pi is potentially P-graphic if there is at least one realization of \pi with property P.

Given a graph H, we will focus on potentially H-graphic sequences, which are sequences in which at least one realization contains H as a subgraph. We more specifically focus on the potential number, which is the minimum degree sum necessary for a graphic sequence to be potentially H-graphic. We will discuss general asymptotic results for the potential number from Ferrara, Lesaulnier, Moffatt and Wenger. We will also discuss several recent stability results before proposing to study several open stability questions. Finally, we consider the potential number problem in the hypergraph space. Specifically, we will review the relatively few results known on the degree sequences of hypergraphs, and proposes tools and techniques that may be useful in exploring the problem.

Speaker: | Nathan Graber |

Affiliation: | University of Colorado Denver |

Location: | SCB 4017 |

Done