Combinatorics Seminar Archives

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 squareG^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.