Monday, September 25 2017
11:00am - 12:15am
Department Seminar
PhD Research Proposal: Nathan Graber

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.
Speaker:Nathan Graber
Affiliation:University of Colorado Denver
Location:SCB 4017


Download as iCalendar

Done