Discrete Math Seminar, Fall 2018

Next Seminar

09/26, 1:00-2:00 pm, WXLR 206, Joel Nishimura, Random graph models with fixed degree sequences: choices, consequences and irreducibility proofs for sampling.

Abstract: Determining which features of an empirical graph are noteworthy frequently relies upon the ability to sample random graphs with constrained properties. Since empirical graphs have distinctive degree sequences, one of the most popular random graph models is the configuration model, which produces a graph uniformly at random from the set of graphs with a fixed degree sequence. While it is commonly treated as though there is only a single configuration model, one sampled via stub-matching, there are many, depending on whether self-loops and multiedges are allowed and whether edge stubs are labeled or not. We show, these different configuration models can lead to drastically, sometimes opposite, interpretations of empirical graphs. In order to sample from these different configuration models, we review and develop the underpinnings of Markov chain Monte Carlo methods based upon double-edge swaps. We also present new results on the irreducibility of the Markov chain for graphs with self-loops, either proving irreducibility or exactly characterizing the degree sequences for which the Markov chain is reducible. This work completes the study of the irreducibility of double edge-swap Markov chains (and the related Curveball Markov chain) for all combinations of allowing self-loops, multiple self-loops and/or multiedges.

Schedule:

08/29, Samantha Dahlberg, Chromatic symmetric functions and $e$-positivity

Abstract: Richard Stanley introduced the chromatic symmetric function $X_G$ of a simple graph $G$, which is the sum of all possible proper colorings with colors $\{1,2,3,\dots \}$ coded as monomials in commuting variables. These formal power series are symmetric functions and generalize the chromatic polynomial. In this talk we will introduce graph colorings, symmetric functions and properties about $X_G$. Further, we will discuss which graphs $G$ have a $X_G$ that can be written as a non-negative sum of elementary symmetric functions, and additionally we will resolve Stanley's $e$-Positivity of Claw-Contractible-Free Graphs. This is joint work with Angele Foley and Stephanie van Willigenburg.

09/12, Jennifer Elder, Generalizing the Futurama Theorem

Abstract: The Futurama episode "The Prisoner of Benda" marks the first time that a theoretical mathematics problem was created for, and solved within the context of, a TV show. Specifically, the Futurama Theorem (or Keeler's Theorem) has to do with inverses of permutations in the symmetric group. We will go over the original theorem as well as new generalizations that did not appear in the show, and hopefully have some fun with permutations.

09/26, Joel Nishimura, Random graph models with fixed degree sequences: choices, consequences and irreducibility proofs for sampling.

Abstract: Determining which features of an empirical graph are noteworthy frequently relies upon the ability to sample random graphs with constrained properties. Since empirical graphs have distinctive degree sequences, one of the most popular random graph models is the configuration model, which produces a graph uniformly at random from the set of graphs with a fixed degree sequence. While it is commonly treated as though there is only a single configuration model, one sampled via stub-matching, there are many, depending on whether self-loops and multiedges are allowed and whether edge stubs are labeled or not. We show, these different configuration models can lead to drastically, sometimes opposite, interpretations of empirical graphs. In order to sample from these different configuration models, we review and develop the underpinnings of Markov chain Monte Carlo methods based upon double-edge swaps. We also present new results on the irreducibility of the Markov chain for graphs with self-loops, either proving irreducibility or exactly characterizing the degree sequences for which the Markov chain is reducible. This work completes the study of the irreducibility of double edge-swap Markov chains (and the related Curveball Markov chain) for all combinations of allowing self-loops, multiple self-loops and/or multiedges.

10/10, J.D. House

Abstract: tba

10/24, Allison Beemer

Abstract: tba

11/07, Susanna Fishel

Abstract: tba