Events

Title: Combinatorial and complexity theoretic aspects of Stabilities and Controllabilities of linear switched systems(discrete and continuous time)

Abstract: I will talk about my "pre-hyperbolic" research, some of it done jointly with Alex Samorodnitsky and Alex Olshevsky.

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: 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: Robustness for hypergraph embeddings via spreadness

Abstract: In joint work with Kang, K\"uhn, Methuku, and Osthus, we proved the following: If $p\geq{C\log^2n/n}$ and $L_{i,j}\subseteq[n]$ is a random subset of $[n]$ where each $k\in[n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i,j\in[n]$, then asymptotically almost surely there is an order-$n$ Latin square in which the entry in the $i$th row and $j$th column lies in $L_{i,j}$.  We prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs.  These results can be understood as stating that these ``design-like'' structures exist ``robustly''.

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.

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, 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: 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: 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: 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).