# Combinatorics Seminar Archives

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

### Summer 2019

Speaker: Sunita Chepuri, University of Minnesota
Date and Time: Wednesday, August 7th 11am–12 pm
Place: Rome 771

Title:  Plabic R-Matrices
Abstract:  Postnikov's plabic graphs in a disk are used to parametrize totally nonnegative Grassmannians. One of the key features of this theory is that if a plabic graph is reduced, the face weights can be uniquely recovered from boundary measurements. On surfaces more complicated than a disk this property is lost. In this talk, we investigate a certain semi-local transformation of weights for plabic networks on a cylinder that preserves boundary measurements. We call this a plabic R-matrix. We explore the properties of the plabic R-matrix, including the symmetric group action it induces on plabic networks and its underlying cluster algebra structure.

### Spring 2019

Title: Two problems regarding primitive sets of integers
Speaker: Nathan McNew, Towson
Date and time: Monday, April 15, 4–5pm
Place: Phillips 736

Abstract: A set of integers is primitive if no integer in the set divides another. The prime numbers form one such a set, but there are many others. Let f(n) count the number of primitive subsets of the integers {1, 2, ... n}. Cameron and Erdos showed that 1.55^n < f(n) < 1.59^n and conjectured that f(n) was asymptotic to c^n for some constant c. In 2017 the conjecture was proven Angelo, but his proof is ineffective in the sense that it gives no information about the value of the constant c. We improve Angelo's result by showing how this constant can be computed and obtaining an error term. Then, we use the probabilistic method to construct infinite primitive sets with relatively small gaps between consecutive terms, substantially smaller than is known to hold for the primes. The techniques we present generalize to a variety of related combinatorial questions.

Title:  On the Intersection Numbers of Finite Groups
Speaker: Lindsey-Kay Lauderdale, Towson
Date and time: Thursday, April 4, 4-5pm
Place: Rome 352

Abstract:  In a popular paper of Cohn, the concept of a covering number of a group was introduced. The covering number of a nontrivial finite group G is the smallest number of proper subgroups of G whose set-theoretic union is G. Covering numbers are the subject of prior research by numerous authors, and in this talk we focus on a dual problem to that of covering numbers of groups, which involves maximal subgroups of finite groups. In addition, we will compare our results to some of the well-known results on covering numbers.  This is joint work with Kassie Archer and Humberto Bautista Serrano.

Title: Quadrangulated Immersions of Cubic Graphs in the Sphere
Speaker: Lowell Abrams, GWU
Date and time: Thursday, March 28, 4–5pm
Place: Rome 352

Abstract: A quadrangulated immersion of a graph G in a surface S is a drawing of G in S so that each crossing is transversal, each point of crossing is formed by exactly two edges, and each connected region of the complement of G in S is bounded by [portions of] four edges of G. We discuss basic constraints on quadrangulated immersions of cubic graphs in the sphere, and demonstrate various methods of constructing such immersions, including methods for constructing non-isomorphic immersions of the same graph. This is joint work with Yosef Berman, Michael Murphy, and Vance Faber.

Title: Quadrangulated Immersions of Cubic Graphs in the Sphere(CANCELLED/RE-SCHEDULED)
Speaker: Lowell Abrams, GWU
Date and time: Thursday, March 7, 4–5pm
Place: Rome 352

Abstract: A quadrangulated immersion of a graph G in a surface S is a drawing of G in S so that each crossing is transversal, each point of crossing is formed by exactly two edges, and each connected region of the complement of G in S is bounded by [portions of] four edges of G. We discuss basic constraints on quadrangulated immersions of cubic graphs in the sphere, and demonstrate various methods of constructing such immersions, including methods for constructing non-isomorphic immersions of the same graph. This is joint work with Yosef Berman, Michael Murphy, and Vance Faber.

Speaker: Chaim Even Zohar, UC Davis
Date and time: Monday, February 25, 4-5pm
Place: Rome 206
Title: Patterns in Random Permutations

Abstract: Every k entries in a permutation can have one of k! different relative orders, called patterns. How many times does each pattern occur in a large random permutation of size n? The distribution of this k!-dimensional vector of pattern densities was studied by Janson, Nakamura, and Zeilberger (2015). Their analysis showed that some component of this vector is asymptotically multinormal of order 1/sqrt(n), while the orthogonal component is smaller. Using representations of the symmetric group, and the theory of U-statistics, we refine the analysis of this distribution. We show that it decomposes into k asymptotically uncorrelated components of different orders in n, that correspond to representations of Sk. Some combinations of pattern densities that arise in this decomposition have interpretations as practical nonparametric statistical tests.

Speaker: Jonathan David Farley, Morgan State University
Date and time: Thursday, February 14, 4-5pm
Place: Rome 352
Title: Does Every Infinite Geometric Lattice of Finite Rank Have a Matching?  A "Challenging Question" of Björner from 1976

Abstract: At the 1981 Banff Conference on Ordered Sets, Anders Björner asked if every geometric lattice of finite rank greater than 1 had a matching between the points and hyperplanes, a question he called "challenging" in 1976.  The matching sought is an injection from points to hyperplanes that matches a point to a hyperplane over it.  We answer Björner's question.

Speaker: Valeriu Soltan, George Mason University
Date and time: Thursday, January 31, 4-5pm
Place: Rome 352
Title: Helly-type results on support lines for families of convex ovals

Abstract: We discuss the following new result of combinatorial geometry: a disjoint family of six or more unit circular disks in the plane has a common support line provided every its subfamily of three disks has a common support line.

Speaker: Emanuele Delucchi, University of Fribourg
Date and time: Thursday, January 24, 4-5pm
Place: Rome 352
Title: Stanley-Reisner rings of symmetric simplicial complexes

Abstract:  A classical theme in algebraic combinatorics is the study of face rings of finite simplicial complexes (named after Stanley and Reisner, two of the pioneers of this field). In this talk I will examine the case where the simplicial complexes at hand carry a group action and are allowed to be infinite. I will present the foundations of this generalized theory with a special focus on simplicial complexes associated to (semi)matroids, where the associated rings enjoy especially nice algebraic properties. A main motivation for our work comes from the theory of arrangements in abelian Lie groups (e.g., toric and elliptic arrangements), and in particular from the quest of understanding numerical properties of the coefficients of characteristic polynomials and h-polynomials of arithmetic matroids. I will describe our current results in this direction and, time permitting, I will outline some open questions that arise in this new framework. (Joint work with Alessio D'Alì.)

Speaker: Gi-Sang Cheon, Sungkyunkwan University
Date and time: Monday, January 14, 4-5pm
Place: Rome 206
Title: On Riordan graphs

Abstract: In this talk, we use the theory of Riordan matrices to introduce the notion of a Riordan graph. The Riordan graphs are a far-reaching generalization of the well known and well studied Pascal graphs and Toeplitz graphs, and also some other families of graphs. The Riordan graphs are proved to have a number of interesting (fractal) properties, which can be useful in creating computer networks with certain desirable features, or in obtaining useful information when designing algorithms to compute values of graph invariants. The main focus in this talk is the study of structural properties of families of Riordan graphs obtained from infinite Riordan graphs, which includes a fundamental decomposition theorem and certain conditions on Riordan graphs to have an Eulerian trail/cycle or a Hamiltonian cycle.

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

### Spring 2018

Speaker: Deborah Chun, West Virginia University Institute of Technology
Date and time: Tuesday, April 24, 1-2pm
Place: Rome 771
Title:  Matroids from Graphs and Graphs from Matroids
Abstract:
In this talk, we will introduce matroids.  Matroid theory generalizes the idea of independence that can come up in various fields, including graph theory.  Theorems in matroid theory often have corollaries that are theorems in graph theory.  An example of this will be given.

If G is a graph, we can construct a matroid from G in multiple ways.  Two matroids from graphs, the cycle matroid and the bicircular matroid, will be defined.  Similarly, if M is a matroid, we can construct multiple graphs from M.  We will define the basis exchange graph of a matroid.  We will give some results for these objects.

Speaker: Felix Lazebnik, University of Delaware
Date and time: Tuesday, April 17, 1-2pm
Place: Rome 771
Title: Cycles in sparse graphs

Abstract:There are several sufficient conditions for a graph on n vertices to contain a cycle of length k, and, in particular, to be Hamiltonian.  Often these conditions do not hold in sparse graphs, i.e., in graphs with the number of edges being o(n^2), as n goes to infinity.  In this talk we present several recent results on the existence of cycles of certain lengths (including Hamiltonian cycles) in some families of sparse graphs, and we state some open problems.

Speaker: Hosam Mahmoud, GW Department of Statistics
Date and time: Tuesday, April 10, 1-2pm
Place: Rome 771
Title: Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment

Abstract: We investigate node degrees in a network grown from a seed by hooking self-similar components under two models of randomness: a uniform model and a model based on preferential attachment.  We study two degree profiles: a local profile tracking the evolution of the degree of a particular node over time, and a global profile concerned about counts of the number of nodes of a particular degree.

For the local profile, under uniform growth, we have the exact mean, variance and probability distribution in terms of standard combinatorial numbers like generalized harmonic numbers and Stirling numbers of the first kind.  Asymptotically, we observe phases:  The early nodes have an asymptotically normal distribution, intermediate nodes have a Poisson distribution and the late nodes have a degenerate distribution.  In contrast, under preferential attachment, the moments of the degree of a node contain Stirling numbers of the second kind and (under appropriate scaling) has a gamma-type limit law.

As for the global profile, we use Polya urns to derive strong laws.  Four regimes arise according to the structure of the seed.  Within these regimes, we identify a few degenerate cases.  Barring these degenerate cases, we uncover an asymptotically normal joint multivarite distribution for nodes of very small degrees.

Speaker: Sebastian Cioaba, University of Delaware
Date and time: Tuesday, April 3, 1-2pm
Place: Rome 771
Title: Spectral characterization of graphs

Abstract:The spectrum of a graph is the multiset of the eigenvalues of its adjacency matrix.  A graph G is determined by its spectrum (DS) if any graph that has the same spectrum as G must be isomorphic to G.  In general, it is a non-trivial problem to determine whether a given graph is DS.  In this talk, I will explain the basic results related to spectral characterization of graphs and describe some of our recent results related to spectral characterization of friendship graphs and graphs in the Johnson association scheme.

Speaker: Kendra E. Pleasant, Morgan State University
Date and time: Tuesday, March 27, 1-2pm
Place: Rome 771
Title: Partitioning the Rainbow

Abstract: Ramsey Theory is a mathematical study of combinatorial objects in which a certain degree of order must occur as the scale of the object becomes large.  A standard problem in Ramsey Theory starts with some mathematical object and breaks it into several pieces. How big must the original object be for the pieces to have a certain property?  This is described as partition regularity.  A major tool used to establish this partition regularity is partition regular matrices.  In this talk, we will get down and dirty with these matrices.  First we will show how these matrices give some of the fundamental results in Ramsey Theory; then we will focus on some new results about these matrices.

Speaker: Lowell Abrams, GWU(CANCELLED)
Date and time: Tuesday, March 20, 1-2pm
Place: Rome 771
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: Dan Cranston, Virginia Commonwealth University
Date and time: Tuesday, March 6, 1-2pm
Place: Rome 771
Title: Coloring Squares of Planar Graphs

Abstract:  The square$G^2$, of a graph $G$ is formed from $G$ by adding an edge joining each pair of vertices at distance 2 in $G$. If $G$ has maximum degree $k$, then $G^2$ can have maximum degree as big as $k^2$ and the chromatic number, $\chi(G^2)$, of $G^2$ can be as big as $k^2+1$. Two examples that achieve equality are the 5-cycle and the Petersen graph. In general these bounds cannot be improved much. For example, if $G$ is the incidence graph of a projective plane and $G$ has maximum degree $k$, then $G^2$ has maximum degree $k^2$ and $\chi(G^2) \approx k^2-k$. However, for planar graphs, we can do much better.

It is easy to show that if $G$ is a planar graph with maximum degree $k$, then $\chi(G^2) \le 9k$; in fact, this bound can be greatly improved. However, constructions show that we cannot improve it beyond $3k/2+1$.  Further, every graph $G$ with maximum degree $k$ trivially satisfies $\chi(G^2)\ge k+1$. We survey various classes of planar graphs for which this trivial lower bound holds with equality or nearly holds with equality. More precisely, we seek a graph class $\mathcal{H}$ and a constant $C$ such that every graph $G\in \mathcal{H}$ with maximum degree $k$ satisfies $\chi(G^2) \le k+C$. Our main result is that if $\mathcal{H}$ is defined by forbidding certain lengths of cycles, then $\mathcal{H}$ has this property if and only if we forbid either (i) 4-cycles or (ii) all even cycles of length at least 6.

This is joint work with Ilkyoo Choi.

Speaker: Joe Bonin, GWU
Date and time: Tuesday, February 20, 1-2pm
Place: Rome 771
Title: Minor-Closed Classes of Polymatroids

Abstract:  A polymatroid is an integer-valued function on the subsets of a set that has all of the properties of a matroid rank function with the possible exception of the cardinality bound.  Some, but not all, polymatroids can be obtained by adding the rank functions of some matroids on the same set.  We explore ideas related to such decompositions of polymatroids; this includes an extension of graph coloring, as well as some excluded-minor results.

Speaker: Patrick Brosnan, University of Maryland
Date and time: Tuesday, February 13, 1–2pm
Place: Rome 771
Title: Tymoczko's dot action on the cohomology of Hessenberg varieties

Abstract: Hessenberg varieties are certain subvarieties of flag varieties.   For GLn, they are defined in terms of an nxn matrix S along with a certain function f from {1,...,n} to itself, which we call a Hessenberg function.  When all of the eigenvalues of the matrix are distinct, the associated Hessenberg variety is smooth and the associated variety B(f,s) comes equipped with an action of the symmetric group first studied by Tymoczko, who called it the "dot action."  In a theoretical sense, Tymoczko's action is computable in terms of a combinatorial object called the moment graph associated to the Hessenberg variety.   But the complexity of actually carrying out such a computation (even using a computer) is rather daunting.  I will explain joint work with Tim Chow proving a conjecture of Shareshian and Wachs, which gives a more or less closed form expression for the action in terms of a chromatic symmetric function associated to a certain graph.  This function is a generalization of Stanley's chromatic symmetric function introduced by Shareshian and Wachs, who were partially motivated by conjectures of Stanley and Stembridge on the e-positivity of Stanley's chromatic symmetric function.   In my talk I will explain some of this, and I will also say a few words about Guay-Paquet's independent proof of the Shareshian–Wachs conjecture (along with a generalization of some of his arguments from the case of GLn to other groups).

Speaker: Craig Larson, Virginia Commonwealth University
Date and time: Tuesday, February 6, 1-2pm
Place: Rome 771
Title: The Graph Brain Project
Abstract: We discuss the use of modern computer tools and resources to systematically advance our shared mathematical goals. In this talk we will discuss the available tools in the context of a summer 2017 project to find bounds for the independence number of a graph.  The independence number is the cardinality of a maximum independent set in a graph. Two conjectured theorems will be discussed, together with a selection of three interesting conjectures.

Speaker: Lou Shapiro, Howard University
Date and time: Tuesday, January 30, 1-2pm
Place: Rome 771
Title: Combinatorics and the Quadratic Formula
Abstract: We explore the connection between the quadratic formula and the Catalan numbers. We start with a piece of folklore, then move to examples including the drunk on the cliff. Then combinatorial interpretations, the Riordan group, and involutions in the Riordan group.

Speaker: Jim Lawrence, George Mason University
Date and time: Tuesday, January 23, 1-2pm
Place: Rome 771
Title: Interval posets, parity representations, binary partitions, and antiprisms
Abstract: Given a poset, one obtains another poset by considering the collection of intervals of the first, partially ordered by inclusion.  (There are various possibilities, depending, for instance, upon whether one considers the empty set as being an interval.'')  This construction has found use in the study of convex polytopes and other places.  We describe a new method of representation of posets by utilizing certain geometric complexes in R^d having vertices in Z^d.  The striking feature of this method of representation is that taking the  interval poset corresponds to dilation by a factor of 2 of the geometric complex.  We explore connections with the integer partitions of powers of 2 into powers of 2.

### 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
Abstract:
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

Abstract:
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.