Combinatorics Seminars

Fall 2019

Speaker: C. Ryan Vinroot, William & Mary
Date and time: Thursday, November 21, 2:15–3:15pm
Place: Phillips 110
Title: Counting real conjugacy classes with generating functions

Abstract: It was noticed by Lehrer (1975) and Macdonald (1981) that the number of conjugacy classes in the finite projective linear group PGL(n,q) is equal to the number of conjugacy classes of GL(n,q) which are contained in SL(n,q), and the number of classes in the finite projective unitary group PGU(n,q) is equal to the number of classes in the finite unitary group U(n,q) which are contained in SU(n,q). Meanwhile, Gow (1981) showed that the number of real classes of GL(n,q) (classes which are inverse-invariant) is equal to the number of real classes of U(n,q). More recently, Gill and Singh (2011) showed that when n is odd or q is even, the number of real classes of PGL(n,q) is equal to the number of real classes of GL(n,q) which are contained in SL(n,q). In this talk, we give a result which generalizes and specializes all of these results. Using generating functions, along with a nice application of Euler's trick, we show that for any n and any q, we have

# real classes of PGL(n,q)
= # real classes of GL(n,q) contained in SL(n,q)
= # real classes of PGU(n,q)
= # real classes of U(n,q) contained in SU(n,q).

This is joint work with my former honors thesis student Elena Amparo, now a PhD student at UC-Santa Barbara in physics.

Speaker: Kevin Long, GWU
Date and time: Thursday, November 14, 2:15–3:15pm
Place: Phillips 110
Title: The Free Cone and its relation to matroid invariants
Abstract: The G-invariant is a matroid invariant that determines the Tutte polynomial, and is of particular interest due to its universality among valuative invariants of matroids. Given a matroid M, we define a new matroid construction called the free cone of M, and prove that its G-invariant is determined by the G-invariant of M. We also look at the configuration, a matroid invariant that determines the G-invariant, and prove that the configuration of M determines the free cone of M.

Speaker: Lou Shapiro, Howard
Date and time: Thursday, November 7, 2:15–3:15pm
Place: Phillips 110
Title: Trees, Leafs, Logs, Palindromes, and the Riordan Group
Abstract: The Riordan group is a useful elementary tool. Some recent applications involve tree structure and a palindromic multiplication for pseudo-involutions.

Title: Graphs and binary matroids whose odd circuits all have size three or five
Speaker: Carolyn Chun, USNA
Date and time: Tuesday, October 29, 1–2pm
Place: Phillips 110

Abstract: Graphs with no odd circuits are well understood. In 1992, Maffray characterized the all graphs whose odd circuits only have size three. Oxley and Wetzler generalized this result to binary matroids in 2016. We give a complete characterization of all binary matroids whose odd circuits all have size three or five, as well as the graphs whose odd cycles all have size three or five. This is based on joint work with James Oxley and Kris Wetzler.

Title: K-Nearest Neighbor Approximation Via the Friend-of-a-Friend Principle
Speaker: Richard W.R. Darling, Math Research Group, NSA
Date and time: Thursday, October 24, 2:15–3:15pm
Place: Phillips 110

Abstract: Suppose $V$ is an $n$-element set where for each $x\in V$, the elements of $V\setminus\{x\}$ are ranked by their similarity to $x$. The $K$-nearest neighbor graph is a directed graph including an arc from each $x$ to the $K$ points of $V\setminus\{x\}$ most similar to $x$. Constructive approximation to this graph using far fewer than $n^2$ comparisons is important for the analysis of large high-dimensional data sets. $K$-Nearest Neighbor Descent is a parameter-free heuristic where a sequence of graph approximations is constructed, in which second neighbors in one approximation are proposed as neighbors in the next. We provide a rigorous justification for $O(n \log n)$ complexity of a similar algorithm, using range queries, when applied to a homogeneous Poisson process in suitable dimension, but show that the basic algorithm fails to achieve subquadratic complexity on sets whose similarity rankings arise from a "generic" linear order on the $\binom{n}{2}$ inter-point distances in a metric space.

Title: Equations for Matroid Varieties
Speaker: Will Traves, USNA
Date and time: Thursday, October 17, 2:15–3:15pm
Place: Phillips 110

Abstract: Gelfand, Goresky, Macpherson and Serganova defined a matroid stratification of the Grassmannian. Matroid varieties, the closure of cells of the stratification, are only partially understood. Even finding equations that vanish on the varieties can be challenging. In this talk, I'll show how to find some equations when the matroid comes from combinatorial arrangements with a very geometric character. The talk will be pitched at an accessible level. This is joint work with Ashley Wheeler and Jessica Sidman (both at Mount Holyoke College).

Title: Divided symmetrization and Schubert polynomials
Speaker: Vasu Tewari, UPenn
Date and time: Thursday, October 10, 2:15–3:15pm
Place: Phillips 110

Abstract: The procedure of divided symmetrization was introduced by A. Postnikov in the context of computing volume polynomials of various classes of permutahedra. This procedure takes a multivariate polynomial as input and outputs a scalar, which in many cases is a combinatorially interesting quantity.

In this talk, I will describe how performing divided symmetrization is equivalent to reducing multivariate polynomials modulo the ideal generated by the homogeneous quasi-symmetric polynomials of positive degree in a fixed number of variables. I will subsequently discuss how divided symmetrization can be used to understand the Schubert expansion of the cohomology class of the Peterson variety. Along the way, we will encounter familiar combinatorial objects such as flagged tableaux, reduced pipe dreams, P-partitions and various Catalan objects.

This is joint work with Philippe Nadeau.

Title: Multiple Zeta Values, Iterated Integrals, and Labeled Posets
Speaker: Michael Hoffman, USNA
Date and time: Thursday, October 3, 2:15–3:15pm
Place: Phillips 110

Abstract: Multiple zeta values are interesting numbers that appear in several areas of mathematics and physics. They can be described as multiple series, and also as iterated integrals. Shuji Yamamoto developed a graphical representation of iterated integrals in terms of labeled posets, an elegant idea that leads to surprising relations. I will describe some implications and extensions of Yamamoto's idea relevant to multiple zeta values.

Title: Doubly weighted rooted trees and computer networks
Date and time: Thursday, September 26, 2:15–3:15pm
Place: Phillips 110

Abstract: Let $T$ be a rooted tree with $n\in{\mathbb N}$ non-root vertices provided with two functions: $p : V(T) \rightarrow{\mathbb Q}$ on the vertices and $c : E(T) \rightarrow {\mathbb Q}$ on the edges, and two fixed numbers $B, G \in {\mathbb Q}^{+}$. We consider the Game-Over Attack Strategy (GOAS) of finding a rooted subtree $T'\subseteq T$ such that $p(T') = \sum_{u\in V(T')}p(u)\geq G$ and $c(T') = \sum_{e\in E(T')}c(e)\leq B$. In general, this decision problem is NP-complete, but that not the whole story. There are numerous special cases that can be solved in polynomial time in n, and these cases can be viewed as models for many security protocols in computer networks. The somber conclusion one can draw from this is that hacking into a computer system is theoretically easy! This is joint work with Ray Greenlaw and Sanpawat Kantrabutra.

Title: The natural matroid of a polymatroid
Speaker: Joe Bonin, GWU
Date and time: Thursday, September 12, 2:15–3:15pm
Place: Phillips 110

Abstract: We show how to use the natural matroid of a polymatroid to develop a theory of circuits for polymatroids, and likewise for a theory of cyclic flats. This is joint work with Tara Fife and Carolyn Chun.

Title: Counting reflections in complex reflection groups
Speaker: Joel Lewis, GWU
Date and time: Thursday, September 5, 2:15–3:15pm
Place: Phillips 110

Abstract: There is a robust field of study involving factorizations of permutations in the symmetric group. One of many results in this area is a formula of Jackson for the generating function that counts factorizations of an n-cycle as a product of k factors, keeping track of the number of cycles in each factor. In this talk, I'll describe joint work with Alejandro Morales on a generalization of this question: we enumerate factorizations of a Coxeter element in a well generated complex reflection group into arbitrary factors, keeping track of the fixed space dimension of each factor. In the infinite families of generalized permutations, our approach is fully combinatorial, while in the other families we use representation-theoretic techniques.

Title: Using the Potential Method to Color Near-Bipartite Graphs
Speaker: Dan Cranston, VCU
Date and Time: Friday, August 30 4–5 pm
Place: Rome 771

Abstract: A graph $G$ is near-bipartite if we can partition $V(G)$ as $(I,F)$ where $I$ is an independent set and $F$ induces a forest. Similar to the problem of 3-coloring, deciding whether a graph is near-bipartite is NP-hard. Thus, we seek sufficient conditions. We show that a multigraph $G$ is near-bipartite if $3|W|-2|E(G[W])|\ge -1$ for every $W\subseteq V(G)$, and $G$ contains no $K_4$ and no Moser spindle. We show that a simple graph $G$ is near-bipartite if $8|W|-5|E(G[W])|\ge -4$ for every $W\subseteq V(G)$ and $G$ contains no subgraph in some finite family (each member of which is not near-bipartite). Each result is very sharp. Namely, if we weaken the lower bound in either hypothesis by 1, then the resulting statement is false infinitely often.

Both results are proved using the potential method, a powerful technique for coloring sparse graphs. As a consequence, both theorems lead to polynomial-time algorithms to find the desired partition. This is joint work with Matthew Yancey.

Archive