Combinatorics Seminar Archives

Fall 2017

Speaker: Alexander Barg, University of Maryland
Date and time: Wednesday, November 29, 4-5pm
Place: Rome 771
Title: Efficient low-degree polynomial interpolation
Abstract: Let f(x) be a polynomial of degree less than k over a finite field Fq. Its value at any given point a in Fq can be found once we know its values at any k other points a_i.  We consider the problem of finding f(a) by observing some partial information about the values of f(x) at d > k points, i.e., some functions g_i(a_i), i=j_1,...,j_d.  We present a construction that gives an optimal solution of this problem (we will discuss the meaning of optimality along the way). The construction relies on specially designed subfields of Fq.  This problem is known in coding theory as the repair problem of Reed-Solomon codes, and we will use coding theoretic language in the description of the solution.  Based on recent joint works with Itzhak Tamo and Min Ye.

Speaker: Joel Brewster Lewis, GWU
Date and time: Wednesday, November 15, 4-5pm
Place: Rome 771
Title: Rook theory of the finite general linear group
Abstract: The combinatorial field of rook theory considers the following questions: given a subset B (called a board) of the discrete n-by-n square, how many ways are there to place r rooks on the board so that no two lie in the same row or column?  And how many of the full placements of n rooks intersect B in exactly r squares?  These numbers, respectively called the rook number and hit number, satisfy a variety of pleasant identities and dualities.

Beginning with work of Garsia and Remmel in the 1980s, combinatorialists have considered q-analogues of these problems, in the following sense: associate to each rook placement P a statistic stat(P), and compute the sum of q^(stat(P)) over all rook placements, where q is a formal variable.  The result is a polynomial in q whose coefficients count rook placements according to stat, and whose value at q = 1 is the rook number.  Haglund showed that for sufficiently nice boards (the so-called Ferrers diagrams), the Garsia--Remmel q-rook number can also be obtained by counting matrices of a given rank whose support is in the board B over a finite field.  In this talk, I'll describe recent work with Morales in which we further investigate this finite field rook theory, including a definition of a q-analogue of the hit numbers and a number of intriguing questions related to positivity of certain formulas.

Speaker: James Shook, NIST
Date and time: Wednesday, November 1, 4-5pm
Place: Rome 771
Title:  Degree Sequence Packing
Two n-vertex graphs G_1 and G_2 pack if it is possible to express G_1 and G_2 as edge-disjoint subgraphs of K_n, or alternatively, if G_1 is a subgraph of the complement of G_2. Let G_1 and G_2 be n-vertex graphs with maximum degrees D_i for i=1,2. A classic conjecture of Bollobas and Eldridge  and, independently, Catlin says that if (D_1+1)(D_2+1)<n+2, then G_1 and G_2 pack. A sequence (d_1,...,d_n) is graphic if there is a simple graph G with vertex set {v_1,...,v_n} such that the degree of v_i is d_i.  We say that G is a realization of the sequence.  In this talk we show that graphic sequence analogs of the classic conjecture hold. In particular, if the inequality above holds, then there exists some graph G_3 with the same vertex degrees as G_2 that packs with G_1.

Note the different day and location!
Speaker: Elizabeth Drellich, Swathmore College
Date and time: Monday, November 64-5pm
Place: Science and Engineering Hall, 7040
Title: The Containment Poset of Hessenberg Varieties

The Hessenberg varieties are an expansive family of subvarieties of the flag variety determined by two parameters: an element X of the Lie algebra g and a subspace H of g.  These two parameters let us encode all sorts of combinatorial data into Hessenberg varieties in order to use geometric methods on combinatorial problems. But while they are powerful tools, even basic questions about Hessenberg varieties, such as when two Hessenberg varieties are equal, can be hard to answer.

This talk will present the containment poset on Hessenberg varieties with a fixed parameter X. We will discuss recent results about the poset's structural relationship to Young's lattice and show that a natural involution of the poset extends to a homeomorphism of algebraic varieties.

Speaker: Lowell Abrams, George Washington University
Date and time: Wednesday, October 254-5pm
Place: Rome 771
Title: Symmetric Spherical Grids
Abstract: If an embedding of a graph G in the sphere is a quadrangulation of the sphere, then G is necessarily bipartite. Assuming that G has minimum vertex degree 3 and that all vertices in one block of V(G) have degree 4, we refer to G as a spherical grid. We discuss general structural properties in spherical grids, then use these to completely characterize rotationally symmetric spherical grids having two vertices of degree n, 2n vertices of degree 3, and all other vertices of degree 4. Furthermore, we show how to represent all possible examples as nets. The talk will feature pictures and props.

Speaker: Carolyn Chun, US Naval Academy
Date and time: Wednesday, October 184-5pm
Place: Rome 771
Title: New directions in delta-matroids
Abstract: Delta-matroids generalize embedded graphs similar to the way that matroids generalize graphs.  In this talk, I will define delta-matroids and give some motivation for recent work in delta-matroid theory, as well as present some new results.

Speaker: Geir Agnarsson, George Mason University
Date and time: Wednesday, October 114-5pm
Place: Rome 771
Title: The flags of Minkowski sums of simplices
Abstract: An interesting class of polytopes that includes various known types of polytopes like hyper-simplices, permutahedra, associahedra and even some matriod base polytopes is formed by the Minkowski sums of simplices in R^n of fixed dimension. These polytopes can further be viewed as a certain building blocks for certain generalized permutahedra. In this talk we discuss the flags of these Minkowski sums and some of their face lattice structure

Speaker: Dan Ullman, GWU
Date and time: Wednesday, October 44-5pm
Place: Rome 771
Title: Differences of bijections
Abstract: Take two permutations in S_n and subtract one from the other as functions modulo n. What kind of function can be obtained in this way? This question was answered by Marshall Hall in the 1950s. We'll look at Hall's theorem and various generalizations, replacing S_n with other abelian groups and replacing permutations with injections or surjections. We will mention Laszlo Fuchs, George Szekeres, graphs, Latin squares, juggling, and bus scheduling. Recent work is joint with Dan Velleman

Speaker: Joe Bonin, GWU
Date and timeWednesday, September 274-5pm
Place: Rome 771
Title:  A New Perspective on the G-Invariant of a Matroid

Abstract:The G-invariant of a matroid was introduced by Derksen (2009), who showed that it properly generalizes the Tutte polynomial.  Derksen and Fink (2010) showed that the G-invariant is universal among invariants that satisfy an inclusion/exclusion-like property (defining valuations) on matroid base polytopes. In this joint work with Joseph Kung, we give a new view of this invariant and explore its implications.  We show that the G-invariant of a matroid M is equivalent to recording the size-increases along all maximal flags of flats of M.  With this, we can determine the effect of some matroid constructions, such as taking q-cones, on the G-invariant, and we can identify some of the information that the G-invariant picks up that the Tutte polynomial does not, such as the number of circuits and cocircuits of any given size, and the number of cyclic flats of any given rank and size.  From its G-invariant, we can tell whether a matroid is a free product of two other matroids (other than free extensions and coextensions).  Also, the G-invariant of a matroid can be reconstructed from the multi-set of G-invariants of the restrictions to hyperplanes.  Still, extending what J.~Eberhardt (2014) proved for the Tutte polynomial, the G-invariant is determined just by the isomorphism type of the lattice of cyclic flats along with the rank and size of each cyclic flat.

Speaker: Alex Burstein, Howard University
Date and timeWednesday, September 204-5pm
Place: Rome 771
Title: Unbalanced Wilf-equivalence

Abstract: A pattern is an equivalence class of permtutaions over a totally ordered alphabet under an order isomorphism. A permutation S avoids a pattern P if it has no subsequence order-isomorphic to P. Two sets of patterns, T_1 and T_2, are Wilf-equivalent if, for each n, they are avoided by same number of permutations of length n. A Wilf-equivalence of sets of patterns T_1 and T_2 is balanced if, for each k, T_1 and T_2 contain the same number of patterns of size k. We will consider some of the smallest cases of unbalanced Wilf-equivalence, and their generalizations to infinite families of unbalanced Wilf-equivalences, as well as some conjectured Wilf-equivalences that are still open problems.

Speaker: Max Wakefield, US Naval Academy
Date and time: Wednesday, September 134-5pm
Place: Rome 771
Title: Matroid Kazhdan-Lusztig polynomials
Abstract:  The classical Kazhdan-Lusztig polynomials have brought a wealth of interesting mathematics for decades. In this talk we will survey a new invariant of a matroid which closely resembles these famous polynomials. These matroid KL polynomials are intersection cohomology Poincare polynomials of an interesting algebraic variety: the reciprocal plane. The Catalan numbers and other interesting combinatorial numbers turn up as coefficients of these polynomials for certain families of matroids. One exciting feature of these polynomials is that at this time there is very little known about their structure and lots of open conjectures. We will highlight some of these conjectures together with some of the examples which provided the motivation.

Speaker: Joel Brewster Lewis, GWU
Date and time: Wednesday, September 64-5pm
Place: Rome 771
Title: Reflection length in affine reflection groups
Abstract: If W is a group generated by a subset T of its elements, the T-length ell_T(w) of an element w in W is the smallest integer k such that w can be written as a product of k elements of T.  In the case that W is a finite Coxeter group (or the real orthogonal group, or the general linear group of a finite-dimensional vector space) with T equal to the set of all reflections in W, this extrinsic notion can be given an intrinsic, geometric definition: the reflection length of w is equal to the codimension of the fixed space, or equivalently to the dimension of its moved space. In the case that W is the symmetric group S_n, reflection length also has a combinatorial interpretation: ell_T(w) = n - c(w), where c(w) is the number of cycles of w.

In this talk, we'll describe a new result (joint with Jon McCammond, Kyle Petersen, and Petra Schwer) extending these results to the case of affine Coxeter groups. Our formula, which has a short, uniform proof, involves two different notions of dimension for the moved space of a group element. In the case that the group is the affine symmetric group, we also give a combinatorial interpretation for these dimensions.