# 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.

Speaker: Richard W.R. Darling, Math Research Group, NSA

Date and time: Thursday, October 24, 2:15–3:15pm

Place: Phillips 110

Abstract: Suppose is an -element set where for each , the elements of are ranked by their similarity to . The -nearest neighbor graph is a directed graph including an arc from each to the points of most similar to . Constructive approximation to this graph using far fewer than comparisons is important for the analysis of large high-dimensional data sets. -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 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 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).

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.

Date and time: Thursday, September 26, 2:15–3:15pm

Place: Phillips 110

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 is near-bipartite if we can partition as where is an independent set and 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 is near-bipartite if for every , and contains no and no Moser spindle. We show that a simple graph is near-bipartite if for every and 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.