#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Monday, July 31, 2023 2:30 PM EDT

**Title: **URA Presentations

Speakers: |
Tom Iagovet, Joseph Vendryes, Jacob Mausberg, Yun Xing |

Affiliation: |
University of Waterloo |

Location: |
MC 5479 |

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

Monday, July 31, 2023 1:00 PM EDT

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

Speaker: |
Matheus Ota |

Affiliation: |
University of Waterloo |

Location: |
MC 6029 |

**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.

Monday, July 31, 2023 11:30 AM EDT

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

Speaker: |
Safet Penjić |

Affiliation: |
University of Primorska |

Location: |
Please contact Sabrina Lato for Zoom link |

**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)$?

Thursday, July 27, 2023 3:00 PM EDT

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

Speaker: |
Lise Turner |

Affiliation: |
University of Waterloo |

Location: |
MC 6029 |

**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.

Monday, July 24, 2023 3:30 PM EDT

**Title: **Robustness for hypergraph embeddings via spreadness

Speaker: |
Tom Kelly |

Affiliation: |
Georgia Tech |

Location: |
MC 5479 |

**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''.

Monday, July 24, 2023 1:00 PM EDT

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

Speaker: |
Matheus Ota |

Affiliation: |
University of Waterloo |

Location: |
MC 6029 |

**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.

Monday, July 24, 2023 11:30 AM EDT

**Title: **Geometric approach to some rank 3 graphs

Speaker: |
Hendrik Van Maldeghem |

Affiliation: |
Ghent University |

Location: |
Please contact Sabrina Lato for Zoom link |

**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.

Friday, July 21, 2023 3:30 PM EDT

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

Speaker: | Leonid Gurvits |

Affiliation: | The City College of New York |

Location: | MC 5501 |

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

Thursday, July 20, 2023 1:00 PM EDT

**Title: **Bipartite determinantal ideals and concurrent vertex maps

Speaker: |
Li Li |

Affiliation: |
Oakland University |

Location: |
MC 5501 |

**Abstract: **The classical determinantal ideals play an important role in commutative algebra, algebraic geometry, representation theory and combinatorics. They can be generalized to bipartite determinantal ideals which are the defining ideals of Nakajima's affine graded quiver variety. In this talk, we will introduce a combinatorial model called concurrent vertex maps to describe the Stanley-Reisner complex of the initial ideal of any bipartite determinantal ideal, and study properties and applications of this model.

Monday, July 17, 2023 2:30 PM EDT

**Title: **Budget Feasible Mechanisms

Speaker: |
Rian Neogi |

Affiliation: |
University of Waterloo |

Location: |
MC 5479 |

**Abstract: **In the setting of budget feasible mechanism design, a buyer wants to purchase items from a set of agents. Each agent can supply at item at an incurred cost of c_i to themself, and the buyer wants to optimize over their own valuation for the set of items bought. The cost c_i is private information that the buyer doesn't have access to. The goal is to design a mechanism that is truthful, in the sense that the sellers do not have incentive to deviate from reporting their true costs, and budget feasible, in the sense that the total payments made to the sellers is within some budget B.

Monday, July 17, 2023 1:00 PM EDT

**Title: **Budget Feasible Mechanisms : Part II

Speaker: |
Rian Neogi |

Affiliation: |
University of Waterloo |

Location: |
MC 6029 |

**Abstract: **In the setting of budget feasible mechanism design, a buyer wants to purchase items from a set of agents. Each agent can supply at item at an incurred cost of c_i to themself, and the buyer wants to optimize over their own valuation for the set of items bought. The cost c_i is private information that the buyer doesn't have access to. The goal is to design a mechanism that is truthful, in the sense that the sellers do not have incentive to deviate from reporting their true costs, and budget feasible, in the sense that the total payments made to the sellers is within some budget B.

Monday, July 17, 2023 11:30 AM EDT

**Title: **On the eigenvalues of the graphs D(5,q)

Speaker: |
Himanshu Gupta |

Affiliation: |
University of Delaware |

Location: |
Please contact Sabrina Lato for Zoom link |

**Abstract: **In 1995, Lazebnik and Ustimenko introduced the family of q-regular graphs D(k, q), which is defined for any positive integer k and prime power q. The connected components of the graph D(k, q) have provided the best-known general lower bound on the size of a graph for any given order and girth to this day.

Thursday, July 13, 2023 3:00 PM EDT

**Title: **To be annouced.

Speaker: |
Josephine Reynes |

Affiliation: |
University of Waterloo |

Location: |
MC 5501 |

**Abstract: **To be announced.

Monday, July 10, 2023 8:00 PM EDT

**Title: **Thin distance-regular graphs with classical parameters $(D,q,q,\frac{q^{t}-1}{q-1}-1)$ with $t> D$ are the Grassmann graphs

Speaker: |
Xiaoye Liang |

Affiliation: |
Anhui Jianzhu University |

Location: |
Please contact Sabrina Lato for Zoom link |

**Abstract: **In the survey paper by Van Dam, Koolen and Tanaka (Distance-regular graphs, Electron. J. Comb., Dynamic Survey (2016), \#DS22), they asked to classify the thin $Q$-polynomial distance-regular graphs. In this talk, we will discuss our result which states that the Grassmann graphs with large diameter are characterized by their intersection numbers under the extra condition that they are thin.

This is joint work with Jack Koolen and Ying-Ying Tan.

Monday, July 10, 2023 2:30 PM EDT

**Title: **Counting matroid extensions

Speaker: |
Shayla Redlin Hume |

Affiliation: |
University of Waterloo |

Location: |
MC 5479 |

**Abstract:** In this talk, we will discuss methods of counting the number of extensions of certain matroids. We will see that, in some cases, the number of extensions is surprisingly large. I will start by introducing matroids, so previous experience with matroids is not assumed.

Monday, July 10, 2023 1:00 PM EDT

**Title: **Budget Feasible Mechanisms

Speaker: |
Rian Neogi |

Affiliation: |
University of Waterloo |

Location: |
MC 6029 |

**Abstract: **In the setting of budget feasible mechanism design, a buyer wants to purchase items from a set of agents. Each agent can supply at item at an incurred cost of c_i to themself, and the buyer wants to optimize over their own valuation for the set of items bought. The cost c_i is private information that the buyer doesn't have access to. The goal is to design a mechanism that is truthful, in the sense that the sellers do not have incentive to deviate from reporting their true costs, and budget feasible, in the sense that the total payments made to the sellers is within some budget B.

Friday, July 7, 2023 3:30 PM EDT

**Title:** Ramsey Cayley graphs, random graph models, and information theory

Speaker: | Jacob Fox |

Affiliation: | Stanford University |

Location: | MC 5501 |

**Abstract:** A graph is Ramsey if its largest clique or independent set is of size logarithmic in the number of vertices. While almost all graphs are Ramsey, there is still no known explicit construction of Ramsey graphs. Alon conjectured that every finite group has a Ramsey Cayley graph.

Thursday, July 6, 2023 1:00 PM EDT

**Title: **Modular representations of the symmetric group and categorification (part I)

Speaker: |
Ben Webster |

Affiliation: |
University of Waterloo/Perimeter Institute |

Location: |
MC 5501 and Zoom - please contact Oliver Pechenik for the Zoom link |

**Abstract:** I'll give two talks on the representations of the symmetric group over small finite fields, in particular, their block structure, with an emphasis on the perspective from categorical actions of Lie algebras. No previous background in modular representation theory will be assumed.

Tuesday, July 4, 2023 2:30 PM EDT

**Title: **Douglas–Rachford Algorithm for Control- and State-constrained Optimal Control Problems

Speaker: |
Bethany Caldwell |

Affiliation: |
University of Waterloo |

Location: |
MC 5501 |

**Abstract: **The Douglas - Rachford algorithm has been applied to many optimization problems due to its simplicity and efficiency but the application of this algorithm to optimal control is less common. In this talk we utilize this method to solve state- and control-constrained linear-quadratic optimal control problems.

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.