Speakers
Keynote speaker - Dr. Linda Lesniak, Western Michigan Unversity
Hamiltonian Properties in k-Partite Graphs
A graph G is said to be Hamiltonian if it is possible to travel through G, visiting each vertex exactly once, and end at the starting vertex.
After a brief historical review of conditions that guarantee that a graph is Hamiltonian (“sufficient conditions”) and the improved versions in bipartite graphs, we will consider the Hamiltonian problem in k-partite graphs. Two major theorems will be presented, one for balanced k-partite graphs and then the extension for general k-partite graphs. These theorems will actually give sufficient conditions for k-partite graphs to be chorded pancyclic, a much stronger cycle property in graphs. Both of these theorems are “best possible”.
Spencer Backman UVM
Flip-free log-concavity for matroids
In 2015 Adiprasito, Huh, and Katz settled the Heron-Rota-Welsh conjecture that the absolute value of the coefficients of the characteristic polynomial of a matroid are log-concave. Their approach was to show that these coefficients can be interpreted as intersection numbers in the Chow ring of a matroid previously introduced by Feichtner and Yuzvinsky. They then establish a K\"ahler package for the Chow ring of a matroid: Poincar\'e duality, the Hard Lefschetz theorem, and the Hodge-Riemann relations, and show that the desired log-concavity follows from the degree 1 part of the Hodge-Riemann relations (the Hodge index theorem). The AHK proof of the K\"ahler package for matroids is inspired by earlier work of McMullen on simple polytopes and thus utilizes a notion of "flipping" which provides a fine interpolation between matroids and projective space. For achieving their goal, AHK prove that the K\"ahler package respects flipping. This impressive program comes at a cost of working with more general objects than matroids which can obscure some combinatorial and geometric information. I will describe joint work with Chris Eur and Connor Simpson where we provide a new proof of the Hodge index theorem for matroids which eschews the use of flipping and thus does not leave the realm of matroids.
Mark Ellingham, Vanderbilt University
Toughness and prism-hamiltonicity of P4-free graphs
Richard Hammack, Virginia Commonwealth University
What makes a diagram commute?
Christian Gaetz, MIT
A combinatorial duality and the Sperner property for the weak order.
A poset is Sperner if it's largest antichain is no larger than it's largest rank. In the 1980's, Stanley used the Hard-Lefschetz Theorem to prove the Sperner property for strong Bruhat orders on Weyl groups. I will describe work in which we prove Stanley's conjecture that the weak Bruhat order on the symmetric group is also Sperner, by exhibiting a combinatorially-defined representation of sl_2 respecting the structure of the weak and strong orders. I will explain how this representation gives rise to a combinatorial duality between the weak and strong Bruhat orders and leads to a strong order analogue of Macdonald's reduced word identity for Schubert polynomials.
This is joint work with Yibo Gao, MIT
Jonathan Gross, Columbia University
Permutation Representations of Maps: History of Monodromy
Yibo Gao, MIT
Separable elements in Weyl groups
We define the notion of a separable element in a finite Weyl group, generalizing the well-studied class of separable permutations. We prove that the upper and lower order ideals in weak Bruhat order generated by a separable element are rank-symmetric and rank-unimodal, and that the product of their rank generating functions gives that of the whole group, answering an open problem of Fan Wei. We also characterize separable elements using pattern avoidance in the sense of Billey and Postnikov.
This is joint work with Christian Gaetz, MIT
Daniel Johnston, Skidmore College
Deranged Matchings
Sandra Kingan, Brooklyn College, CUNY
Finding monarchs for excluded minor classes of matroids
In a paper that appeared last year I used The Strong Splitter Theorem (joint with Manoel Lemos and published in 2014) to give another proof of Oxley's result that the class of binary matroids with no 4-wheel minor consists of a few small matroids and an infinite family of maximal 3-connected rank r matroids known as the binary spikes. Such a family is called a monarch for the excluded minor class. The proof of Oxley's result comes down to finding the monarchs for non-regular matroids with no minors isomomorphic to a 9-element rank 4 matroid known as P9 or its dual P9*. Subsequently I was able to obtain an if and only if characterization of the class of binary non-regular matroids with no minor isomomorphic to just P9*. I proved that the only members of this class are the rank 3 and 4 binary projective geometries, a 16-element rank 5 matroid, and two monarchs: the rank r binary spikes with 2r+1 elements and another infinite family with 4r-5 elements. This is one of few excluded-minor classes for which the members are so precisely determined. As a consquence if M is a simple binary matroid of rank at least 6 with no P9*-minor, then the number of elements in M is at most r(r+1)/2 and this bound is attained by the rank r complete graph.
Alex McDonough, Brown University
Chip-Firing on Cell Complexes and Matroids
Abstract: Graphical chip-firing has been explored extensively in a variety of contexts. A more recent project has been to extend chip-firing to more general objects, specifically cell complexes and regular matroids. The goal of this talk will be to discuss these two perspectives and how they relate to traditional chip-firing.
Hunter Rehm, UVM
Rainbows in Graph Products
Ramsey Theory is a branch of mathematics whose main questions are of the form: If a system is chaotic or random and we partition the system into smaller pieces can we guarantee that the smaller pieces are no longer chaotic or have some nice structure? Anti-Ramsey Theory type problems ask the opposite questions: If a system is structured and we partition the system into smaller pieces can we guarantee that the smaller pieces break the structure? The open question that we focused on looked at was an anti-Ramsey type question. We wanted to find out exactly how much structure we could give a system before we could guarantee that a smaller piece of our system must break the structure. Our structure breaking pieces are called rainbow 3-term arithmetic progression. We developed tools (theorems) to study the system of graphs called grid graphs (think of an array or a well-planned city with a Google maps view). We eventually answered the open question for all m by n grid graphs and found an upper bound for any graph product!
Lauren Rose, Bard College
SET and SuperSET
Abstract: SET is a card game that has been well studied in terms of its geometric, combinatorial and algebraic properties. We describe some of these properties, and then introduce a variant, SuperSET, where each attribute has 4 states rather than 3. With certain modifications, we are able to prove similar results for SuperSET.
Thomas Tucker, Colgate University
Permutation Representations of Maps: History of Monodromy