Future students

Title: URA Presentations

Abstract: A series of presentations by a group of Spring 2023 Undergraduate Research Assistants. The topics of each presentation are detailed below.

Quantum Max-Cut on Bipartite Graphs - Benjamin Wong

Title: From the Upper Bound Conjecture to Gorenstein linkage

Abstract: In 1957, Motzkin conjectured that the maximum number of faces possible for a polytope on n vertices in d-space is achieved by the convex hull of n points on the moment curve in d-space.  This conjecture, called the Upper Bound Conjecture, was proved by McMullen in 1970 and generalized by Stanley in 1975.  On the road to Stanley's proof, a correspondence between squarefree monomial ideals and simplicial complexes was born.  That correspondence is called the Stanley--Reisner correspondence.  It has come to occupy a central place in combinatorial algebraic geometry. 

Title: Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios, Part II

Abstract: Following state-of-the-art exact algorithms for vehicle routing problems, several recent exact algorithms for the two-stage vehicle routing problem with stochastic demands (VRPSD) are based on set partitioning formulations. To solve the corresponding LP relaxation, these algorithms rely on efficient routines for solving the associated pricing problems. In this paper, we study the complexity of solving such VRPSD pricing problems.

Title: Rigidity of Simplicial Complexes

Abstract: A simplicial k-cycle is an abstract simplicial k-complex in which every (k-1)-face belongs to an even number of k-faces. A simplicial k-circuit is a minimal simplicial k-cycle (in the sense that none of its proper subcomplexes are simplicial k-cycles).

Title: Specializations of Macdonald polynomials using multiline queues and multiline diagrams

Abstract: Multiline queues were introduced by Ferrari and Martin to model the stationary states of the TASEP, a 1D non-equilibrium particle model. Later, Corteel, Mandelshtam, and Williams gave a formula for the Macdonald polynomial using a (X,q,t)-weighted version of multiline queues. This talk aims to develop the combinatorics of such objects in the t=0 case.

Title: URA Presentations

Abstract: A series of presentations by a group of Spring 2023 Undergraduate Research Assistants. The topics of each presentation are detailed below.

Title: Short note about commutative association schemes and specific (directed) family of graphs

Abstract: In this talk, we consider the following problem:

{\bf Problem.} When the Bose--Mesner algebra ${\cal M}$ of commutative $d$-class association scheme ${\mathfrak X}$ (which is not necessarily symmetric) can be generated by a $01$-matrix $A$? With other words, for a given ${\mathfrak X}$ can we find $01$-matrix $A$ such that ${\cal M}=(\langle A\rangle, +, \cdot)$?

Title: Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios

Abstract: Following state-of-the-art exact algorithms for vehicle routing problems, several recent exact algorithms for the two-stage vehicle routing problem with stochastic demands (VRPSD) are based on set partitioning formulations. To solve the corresponding LP relaxation, these algorithms rely on efficient routines for solving the associated pricing problems. In this paper, we study the complexity of solving such VRPSD pricing problems.

Title: Geometric approach to some rank 3 graphs

Abstract: Rank 3 graphs are graphs whose full automorphism group acts as a rank 3 group on the vertices. Finite rank 3 groups are classified and hence finite rank 3 graphs are classified. The main examples arise from geometric structures such as projective and polar spaces, and there is one class of examples related to the exceptional groups of type E6. We present a combinatorial/geometric/projective construction of these graphs.  We then consider a class of regular sets, that is, subsets S of the vertices such that the number of vertices of S adjacent to some vertex v only depends on whether v belongs to S or not. We will explain how this leads to characterizations of certain automorphisms of the E6 graphs and other graphs.

Title: Cluster chromatic number of $G(n,p)$

Abstract: A colouring of a graph $G$ is said to be $\kappa$-clustered if no colour class has a connected component with more than $\kappa$ vertices. In this talk, we give the $\kappa$-clustered chromatic number of $G(n,p)$ for $\kappa$ increasing at various rates with respect to $n$.

The talk is joint work with Jane Gao.