Discrete Math Seminar, Fall 2018

Next Seminar

11/07, 1:00-2:00 pm, WXLR 206, Susanna Fishel, Enumerations relating braid and commutation classes

Abstract: The set of reduced words of a permutation possesses a rich combinatorial structure that has been studied from many differrent perspectives. Quotients of this set under the Coxeter relations hold particular interest, but most work has focused on the commutation classes. I will discuss recent work with Mile 'cevi\'c, Patrias, and Tenner. We obtain an upper and lower bound for the number of reduced words for a permutation in terms of the number of braid classes and the number of commutation classes of the permutation. We classify the permutations that achieve each of these bounds, and enumerate both cases.

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.

Slides

10/10, J.D. House, A Statistic on a Super Catalan Structure

Abstract: The Super Catalan numbers are a known set of numbers which have so far eluded a combinatorial interpretation. Several weighted interpretations have appeared since their discovery, one of which discovered by William Kuszmaul. In this paper, we connect the weighted Super Catalan structure created previously by Kuszmaul and a natural q-analogue of the Super Catalan numbers. We do this by creating a statistic on the set described by Kuszmaul, and in doing so, we take a step towards finding a strict combinatorial interpretation for the Super Catalan numbers.

10/24, Allison Beemer, Absorbing Sets of Codes from Finite Geometries

Abstract: Error-correcting codes seek to address the problem of transmitting information efficiently and reliably across noisy channels. Among the most competitive codes developed in the last 70 years are low-density parity-check (LDPC) codes, a class of codes whose structure may be represented by sparse bipartite graphs. LDPC codes offer the significant practical advantage of low-complexity graph-based decoding algorithms. Graphical substructures called trapping sets, absorbing sets, and stopping sets characterize failure of these algorithms at high signal-to-noise ratios. In this talk, we examine the presence of absorbing sets in LDPC codes constructed from finite geometries.

11/02, Volkmar Welker, The determinant of the Varchenko Matrix for oriented matroids

Abstract: We generalize the Varchenko matrix of a hyperplane arrangement to oriented matroids. We show that the celebrated determinant formula for the Varchenko matrix, first proved by Varchenko, generalizes to oriented matroids. It follows that the determinant only depends on the matroid underlying the oriented matroid and analogous formulas hold for cones in oriented matroids. We follow a proof strategy for the original Varchenko formula first suggested by Denham and Hanlon. Besides several technical lemmas this strategy also requires a topological result on supertopes which is of independent interest.

There will also be a colloquium talk on 11/01, 4:30- 5:30, WXLR A21:

Volkmar Welker, Orthogonal representations of graphs and ideals of minors   (joint work with Aldo Conca)

Abstract: An orthogonal representation of a graph is a map from the vertex set of an undirected graph to d-dimensional real space such that vertices not connected by an edge are sent to orthogonal vectors. Lovasz defined this concept in the 70s motivated by the study of the Shannon capacity of a graph. Optimizing over all orthonormal representations allowed him to define the Lovasz number of a graph. Later joint with Saks and Schrijver he studied the set of all orthogonal representations of a given graph from a geometric point. We follow up on this from the algebraic side and provide results on the limiting behavior of the defining ideal of orthogonal representations when d goes to infinity. We also exhibit relations to ideals of minors. The talk will focus on introducing orthogonal representations and recalling their motivation. Then we will introduce the geometric perspective of Lovasz, Saks, Schrijver before we come to our own results at the end.

11/07, Susanna Fishel, Enumerations relating braid and commutation classes

Abstract: The set of reduced words of a permutation possesses a rich combinatorial structure that has been studied from many differrent perspectives. Quotients of this set under the Coxeter relations hold particular interest, but most work has focused on the commutation classes. I will discuss recent work with Mile 'cevi\'c, Patrias, and Tenner. We obtain an upper and lower bound for the number of reduced words for a permutation in terms of the number of braid classes and the number of commutation classes of the permutation. We classify the permutations that achieve each of these bounds, and enumerate both cases.