Combinatorics Seminars

Fall 2018

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.