Combinatorics Seminars

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.


 

Archive