KU Combinatorics Seminar
Fall 2022

Friday 8/26
Organizational meeting

Friday 9/2
Vance Gaffar (Baker University)
Counting embeddings of graphs in state space

Abstract: We will define a labeled digraph \(G(b)\) on infinite binary strings with \(b\) 1's called \(b\)-ball state space. For a fixed digraph \(g\) we will calculate the number of embeddings of \(g\) into \(G(b)\) as \(b\) approaches infinity. It is commonly believed that the number of embeddings of \(g\) into \(G(b)\) is eventually a polynomial in \(b\), we will prove this for certain classes of graphs.

Friday 9/9
Hailong Dao
Fractals and syzygies

Abstract: The Sierpinski gasket is a construction that appears in a number of mathematical contexts: fractal geometry, number theory (odd entries in the Pascal triangle), game theory (the Tower of Hanoi), and more. In this talk I will explain a new sighting of this object: when one tries to construct optimal monomial ideals with linear presentations. This is joint work with David Eisenbud.

Friday 9/16
No seminar

Friday 9/23
Aaron Ortiz
The Defective Parking Space: Tableaux and Catalan Convolutions

Abstract: Parking functions and their enumerative properties have been studied in depth in the field of combinatorics and in computer science as they are connected to the study of hashing functions. A well-studied result is the Catalan parameterization of the number of orbits of the standard parking space, the set of parking functions under the action of the symmetric group. We will introduce \(d\)-defective parking spaces, showing that defect is an invariant with regards to permutations. We establish a connection between the orbits of \(d\)-defective parking space and standard Young tableaux of shape \((n+d, n-d-1)\). Additionally, we provide a recursive formula for the number of orbits decomposing the \(d\)-defective parking space and establish an interesting link to Catalan convolutions.

Friday 9/30
Brandon Lee
Laplacian Eigenvalues of Bipartite Kneser-Like Graphs

Abstract: The bipartite Kneser-like graph \(G(a,b)\) is constructed as follows. For any integers \(a>b>1\), let \(n=a+b+1\), then let \(\mathcal{A}\) be a set of all \(a\)-sized subsets of \([n]\). Similarly let \(\mathcal{B}\) be the set of all \(b\)-sized subsets of \([n]\). Draw an edge between a vertex in \(\mathcal{A}\) and a vertex in \(\mathcal{B}\) if their intersection is disjoint. We conjecture that all the eigenvalues of the Laplacian matrix of this graph, denoted \(L(G(a,b))\), are all non-negative integers.

We further conjecture a more precise formula for the multiplicity of any eigenvalue and what all the general eigenvalues are. Thus far, we have proved that: every eigenvector has a related pair with a similar eigenvalue and eigenvector, which implies the sequence of multiplicities is symmetric; that all the eigenvalues of \(L(G(a,2))\) are non-negative integers; established a transformation to a smaller matrix; and showed found a general formation of the eigenvector for any eigenvalue of \(L(G(a,b))\).

Friday 10/7
No seminar (Fall Break)

Friday 10/14
Marge Bayer
Perfect Matching Complexes of Honeycomb Graphs

Abstract: A perfect matching of a graph is a collection of edges, no two of which share a vertex. The perfect matching complex of a graph is the simplicial complex on the edge set of the graph with facets corresponding to perfect matchings of the graph. A honeycomb graph is the graph of a hexagonal tiling of a bounded region of the plane. In this talk, I give classes of honeycomb graphs whose perfect matching complexes are contractible or homotopy equivalent to a wedge of spheres. This is joint work with Marija Jelić Milutinović and Julianne Vega.

Friday 10/21
Jeremy Martin
Matroids, polytopes, and beyond

Abstract: Given a matroid \(M\) on ground set \(E=[n]\) with basis system \(\mathcal{B}\), the base polytope \(P_M\subset\mathbb{R}^n\) is the convex hull of the characteristic vectors of the bases. Base polytopes offer a geometric way of looking at matroids with a different flavor than the standard combinatorial cryptomorphisms. These polytopes are a special case of the generalized permutahedra or polymatroids introduced independently by Edmonds and Postnikov; these things in turn are a special case of submodular systems. I will give an overview of all these lovely objects. If time permits, I will discuss ongoing work of Jonah Berggren, Jose Samper, and myself about another kind of submodular generalization of matroids.

Friday 10/28, Snow 306
No seminar

Friday 11/4
Mark Denker
Cut Complexes and Total Cut Complexes of Graphs

Abstract: We define the \(k\)-cut complex of a graph\(G\)as the simplicial complex whose facets are the complements of disconnected sets of size \(k\) in \(G\). We define the total \(k\)-cut complex of a graph\(G\)as the simplicial complex whose facets are the complements of independent sets of size \(k\) in \(G\). Both complexes are generalizations of the complexes developed by Eagon and Reiner to prove Fröberg's theorem. In this talk we study the topological properties of these complexes and their relation to graph properties.

Friday 11/11
Tom Mahoney (Emporia State University)
Studying Combinatorial Games with SageMath

Abstract: Participants are encouraged to bring a laptop with SageMath installed locally or have a CoCalc account to be able to follow along with the demonstrations. (Both of these are free -- talk to Jeremy if you need help.)

In this workshop, we will basic solution algorithms and optimizations for memoization and automorphism checking. We'll see how to study open problems, using computational results to guide conjectures and proofs. In addition to algorithms for solving game positions, we'll develop practical tools for displaying intermediate results. After applying these ideas to a simple example game, we'll see how to apply these techniques for online list coloring (paintability) of graphs.

Jupyter notebook from Tom Mahoney's talk

Friday 11/18
Jin-Cheng Guu (Stony Brook University)
A very general yet mysterious operation on incidence algebras

Abstract: Partially ordered sets (posets) are combinatorial structures underlying many mathematical problems: subdivisions of complexes, matroids (e.g., graphs), representation theory and algebraic geometry of Coxeter type objects (e.g., semisimple Lie algebras and symmetric group). An invariant of a poset is its incidence algebra, which contains much computable information about the poset itself.

In this talk, we will discuss a very general operation on the invertible elements in the incidence algebra. This operation generalizes the celebrated Kazhdan-Lusztig (KL) polynomials from the Coxeter group to all finite graded posets. Time permitting, we will show examples on how they apply to combinatorics (subdivision of complexes, (local) h-vector), matroid theory (q-deformed Mobius algebra in particular), representation theory and algebraic geometry.

Friday 11/25
No seminar (Thanksgiving)

Friday 12/2
Dania Morales
Lattice Path Matroids and Ehrhart Theory

Abstract: In this talk, we focus on matroid base polytopes of lattice path matroids. We will describe two approaches to discuss their Ehrhart theory. For the first approach, we give a description of the base polytope in terms of flats. For the second approach, we give a base polytope decomposition.

Friday 12/9 (Stop Day)
Stephen Lacina (University of Oregon)
Maximal Chain Descent Orders

Abstract: We introduce a new partial order called the maximal chain descent order on the maximal chains of any finite, bounded poset with an EL-labeling. We prove that the maximal chain descent order encodes via its linear extensions all shellings of the order complex induced by the EL-labeling strictly including the well-known lexicographic shellings. We show that the standard EL-labeling of the Boolean lattice has maximal chain descent order isomorphic to the type A weak order. We also prove that natural EL-labelings of intervals in Young's lattice give maximal chain descent orders isomorphic to partial orders on the standard Young tableaux or standard skew tableaux of a fixed shape given by swapping certain entries. We additionally show that the cover relations of maximal chain descent orders are generally more subtle than one might first expect, but we characterize the EL-labelings with the expected cover relations including many well-known families of EL-labelings.

For seminars from previous semesters, please see the KU Combinatorics Group page.

Last updated Fri 11/25/22