Combinatorics Seminars

Fall 2018

Speaker: Lowell Abrams, GWU
Date and time: Thursday, November 1, 4-5pm
Place:  Phillips 110
Title: Searching for Trialities of Embedded Graphs

Abstract: The actions of dualizing and Petrie-dualizing carry one isomorphism class of graph embeddings to another. These operations generate a group isomorphic to S_3 called the Wilson group, and the order-3 elements in the Wilson group are called trialities. Historically, it has been hard to find graph embeddings that are self-trial -- fixed by the trialities -- but not also self-dual and self-Petrie-dual.

In this talk, I will describe the theoretical framework Jo Ellis-Monaghan (St. Michael's College) and I developed to tackle the problem of finding graph embeddings of this elusive type, as well as a variety of bijections and construction techniques we used in conjunction with the theoretical framework to successfully implement a computer search to find all self-trial but non-self-dual and non-self-Petrie-dual embeddings with up to seven edges. As far as we can tell, none of these has ever been found before.

Speaker: Cheyne Homberger, UMBC
Date and time: Thursday, November 8, 4-5pm
Place:  Phillips 110
Title: Permuted Packings and Permutation Breadth

Abstract: The breadth of a permutation π is the minimum value of |i - j| + |π(i) - π(j)|, taken over all relevant i and j. Breadth has important consequences to permutation pattern containment, and connections to plane tiling.  In this talk we explore the breadth of random permutations using both probabilistic techniques and combinatorial geometry.  In particular, we present the expected breadth of a random permutation, the proportion of permutations with a fixed breadth, and a constructive proof for maximizing unique large patterns in permutations.  This talk is based on work with both David Bevan and Bridget Tenner and with Simon Blackburn and Pete Winkler.

Speaker: Alex Burstein, Howard University
Date and time: Thursday, October 25, 4-5pm
Place:  Phillips 110
Title: Involutions and pseudo-involutions in the Riordan group

Abstract:  We define the Riordan group and consider its involutions and pseudo-involutions, as well as A- and B-sequences of Riordan matrices. We then look at one elementary method, via palindromes, for producing pseudo-involutions associated with many well-known combinatorial sequences.  This unified approach yields both classical cases and new(er) examples, some with interesting combinatorial interpretations.  Finally, we give a combinatorial interpretation of some pseudo-involutions via Parker's generalization of the Carlitz-Scoville-Vaughn theorem.  This is joint work with Lou Shapiro.

Speaker: GlennHurlbert, VCU
Date and time: Thursday, October 18, 4–5 pm
Place: Phillips 110
Title: Injective Proofs of the Erdos-Ko-Rado and Hilton-Milner Theorems

Abstract: Let F be a family of r-subsets of {1, 2, ..., n}. We say that F is intersecting if every pair of its sets intersect. The special case when some element (its center) is in each of its sets is called a star. The Erdos-Ko-Rado Theorem (1961 [really 1938]) states that, when n > 2r, the largest intersecting family is a star. The Hilton-Milner Theorem (1967) states that, when n > 2r, the largest non-star intersecting family is a near-star: a star with an extra set not containing its center. Vikram Kamat and I recently devised the first injective proofs of these classical results. I will share them with you in this talk. I'll also discuss some recent work with Fishel, Kamat, and Meagher on variations of the Erdos-Ko-Rado Theorem with other structures, such as permutations, trees, etc.

Speaker: Justin Allman, USNA
Date and time: Thursday, October 11, 4–5 pm
Place: Phillips 110
Title: Counting partitions, Dynkin diagrams, quantum dilogarithms, and generalizations

Abstract: The Durfee's square identity is an effective way to iteratively count partitions going back to at least Cauchy. In this talk we show how this identity is related to representations of a certain quiver, namely an orientation of the A_2 Dynkin diagram. Furthermore, we show that identities among quantum dilogarithm series, with a rich history in their own right, can encode infinitely many of these Durfee's-square-type identities simultaneously. Finally, we discuss how these identities generalize to entire families of quivers.

Speaker: Joel Brewster Lewis, GWU
Date and time: Thursday, October 4, 4–5 pm
Place: Phillips 110
Title: Affine evacuation

Abstract: Evacuation (or Schützenberger's involution) is an involution on standard Young tableaux of a given shape, closely tied to the combinatorics of permutations via the RSK correspondence. One of its many nice features is that the number of fixed points of shape lambda is equal to the number of domino tableaux of the same shape, and is given by evaluating the natural q-analogue of the hook-length formula (counting all tableaux of shape lambda) at q = −1.

In this talk, I'll describe a related involution on tabloids (which are just like tableaux, but with only the row condition). This involution is related to the combinatorics of the affine symmetric group via a generalization of the RSK correspondence. We show that it has many desirable properties; in particular, the number of its fixed points of shape lambda satisfies a domino-like recurrence and is given by an evaluation of a Green polynomial at q = −1.

This talk is based on work with Michael Chmutov, Gabriel Frieden, and Dongkwan Kim.

Speaker: Erik Slivken, Paris VII
Date and time: Thursday, September 27, 4-5pm
Place:  Phillips 110
Title: The local limit of the fixed-point forest

Abstract: We begin with a simple sorting algorithm on a randomly ordered stack of cards labeled 1 through n. If the first card is labeled k, slide that card into the kth position. Repeat until the first card is a 1. This algorithm induces a directed forest structure on the set of permutations. The local limit of this structure converges to a random tree which itself can be constructed directly from a sequence of Poisson point processes. We are able to compute a variety of statistics related to this tree, such as the distribution of the longest and shortest path to a leaf, or its expected size. We also study generalizations of this random tree.

Speaker: Walter Morris, George Mason University
Date and time: Thursday, September 20, 4-5pm
Place:  Phillips 110
Title: A proof of the strict monotone 5-step conjecture

Abstract:  The strict monotone d-step conjecture for linear programming says that, given a d-dimensional polytope P with 2d facets and a linear function f, there is a path in the graph of P from the vertex with minimum f value to the vertex with maximum f value that is increasing in f and contains at most d edges.  Santos (2012) showed that this conjecture is false for d sufficiently large, but the largest d for which it is true is not known.  For d=5 we created a logical statement that is unsatisfiable if there is no counterexample.  The satisfiablility solver that we used showed that there is no counterexample. 

Speaker: Franklin Kenter, US Naval Academy
Date and time: Thursday, September 13, 4-5pm
Place:  Phillips 110
Title: Zero Forcing: Minimum Rank Problems, Sample Error, Combinatorial Optimization, and More.

Abstract: In this talk, I will give an overview of zero forcing in graphs.  What zero forcing is is not important.  Rather, zero forcing appears, as the title suggests, to be at the intersection of many facets in combinatorics, and even mathematics more broadly.  The goal of this talk will be to inspire you to consider zero forcing in your next pursuit of research.
Some results are joint work with Randy Davila and Jephian C-H. Lin.

Speaker: J. Bonin, GWU
Date and time: Thursday, September 6, 4-5pm
Place:  Phillips 110
Title: Presentations and Extensions of Transversal Matroids

Abstract: If a matroid M can be represented over a field F by the columns of a matrix A, then the choice of the matrix can limit which single-element, rank-preserving extensions of M can be represented by adjoining a column to A.  We consider analogous ideas for transversal matroids and their presentations.  Sufficient background on transversal matroids will be included to make the talk largely self-contained.