Events

Title: Lexicographic products, wreath products, and generalisations

Abstract:

I will present a history and overview of some of the work that has been done on the lexicographic product of graphs, and related generalisations. The focus of my talk will be on the automorphism groups of such graphs, and the relationship to the wreath product of permutation groups.

Title: Equivalences of Wilson loop diagrams

Abstract:

I will talk about Wilson loop diagrams, explain a bit about what they are, and some of the combinatorial questions that come out of them, with a focus on when they are equivalent.  This is joint work with Susama Agarwala and Zee Fryer.

Title: An approximate solution to a 2,079,471-point traveling salesman problem

Abstract:

Together with Keld Helsguan, we have found a TSP tour through the 3D positions of 2,079,471 stars. We discuss how linear programming allows us to prove the tour is at most a factor of 0.0000074 longer than an optimal solution. The talk will focus on the use of minimum cuts and GF(2) linear systems, to drive the cutting-plane method towards strong LP relaxations.

Title: The chromatic index of strongly regular graphs (joint work with Sebastian M. Cioaba and Krystal Guo)

Abstract:

It follows from Vizing's theorem that the chromatic index (edge chromatic number) of a k-regular graph equals k or k+1, and that it equals k+1 if the graph has odd order.

We investigate the chromatic index of strongly regular graphs (SRGs) of even order.

Title: The Poset Conjecture: results, counterexamples, and open problems

Abstract:

In 1978, Neggers conjectured that a certain transform of the order polynomial of a partially ordered set (poset) has only real roots.

In the late 1980s, Stanley gave this to me as a thesis project, generalized to labelled posets.  For my thesis I proved the conclusion for series-parallel labelled posets and a bit more.  Br\"and\'en, and later Stembridge, found counterexamples to the conjecture in general.

Title: Decompositions of Hypergraphs

Abstract:

Several results on approximate decompositions of hypergraphs are presented including decompositions into tight Hamilton cycles under very mild assumptions on the host hypergraphs as well as further results on decompositions of quasirandom hypergraphs into bounded degree hypergraphs.

Title: Centrosymmetric Stochastic Matrices

Abstract:

We consider the convex subset of m by n stochastic matrices that are centrosymmetric: stochastic matrices that are symmetric under rotation by 180 degrees. We consider the extreme points and bases of this set, as well as several other parameters associated to such matrices. We provide examples illustrating the results throughout. This is joint work with Lei Cao (Nova Southeastern University) and Darian McLaren (University of Waterloo).

Title: An Efficient Algorithm for Deciding the Vanishing of Schubert Polynomial Coefficients

Abstract:

 Schubert polynomials form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. The vanishing problem for Schubert polynomials asks if a coefficient of a Schubert polynomial is zero. We give a tableau criterion to solve this problem, from which we deduce the first polynomial time algorithm. These results are obtained from new characterizations of the Schubitope, a generalization of the permutahedron defined for any subset of the n x n grid. In contrast, we show that computing these coefficients explicitly is #P-complete. This is joint work with Anshul Adve and Alexander Yong.

Title: Why are Hoffman's bounds for alpha and chi truly duals of each other?

Abstract:

Two of the most well known eigenvalue bounds for graph parameters look suspiciously related. Our goal in this talk is to confirm this suspicion by casting these bounds into a framework of semidefinite optimization that will give us almost for free a duality relation. As one should always expect in this context, we will see a connection to the Lovász theta function of a graph.

Title: A combinatorial approach to Minkowski tensors of polytopes

Abstract:

Intrinsic volumes of a convex body provide scalar data (volume, surface area, Euler characteristic, etc. ) about the geometry of a convex body independent of the ambient space. Minkowski tensors are the tensor-valued generalization of intrinsic volumes. They provide more complex geometric information about a convex body, such as its shape, orientation, and more.