#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Friday, September 30, 2022 3:30 PM EDT

**Title:** The Integrality Gap for the Santa Claus Problem

Speaker: | Penny Haxell |

Affiliation: | University of Waterloo |

Location: | MC 5501 or contact Melissa Cambridge for Zoom link |

**Abstract: **

In the max-min allocation problem, a set of players are to be allocated disjoint subsets of a set of indivisible resources, such that the minimum utility among all players is maximized. In the restricted variant, also known as the Santa Claus Problem, each resource (``toy'') has an intrinsic positive value, and each player (``child'') covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy

jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.

Friday, September 30, 2022 12:00 PM EDT

**Title:** Stochastic Probing with Applications

Speaker: | David Kalichman |

Affiliation: | University of Waterloo |

Location: | MC 6029 or contact Rian Neogi for the Zoom link |

**Abstract:** We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active.

Monday, September 26, 2022 11:30 AM EDT

**Title:** Automorphisms of direct products of some circulant graphs

Speaker: | Dave Witte Morris |

Affiliation: | University of Lethbridge |

Location: | contact Sabrina Lato for Zoom link |

**Abstract:** The direct product of two graphs X and Y is denoted X x Y. Its automorphism group contains a copy of the direct product of Aut(X) and Aut(Y), but it is not known when this inclusion is an equality, even for the special case where X is a circulant graph and Y = K_2 is a connected graph with only 2 vertices.

Friday, September 23, 2022 3:30 PM EDT

**TItle:** A perfect graph, a sparse, symmetric matrix and a homogeneous cone walk into a bar … together??

Speaker: | Levent Tuncel |

Affiliation: | University of Waterloo |

Location: | MC 5501 |

Abstract: The talk title above sounds like the beginning of a corny joke; however, in this talk, we will indeed utilize results from a very large number of research areas. Many of these research areas are directly within Combinatorics and Optimization and some are from other areas covered in the rest of the Faculty of Mathematics.

Friday, September 23, 2022 12:00 PM EDT

**Title:** On the Adaptivity Gap of Stochastic Orienteering

Speaker: | Paul Lawrence |

Affiliation: | University of Waterloo |

Location: | MC 6029, please contact Rian Neogi for Zoom link |

Abstract: This talk highlights the *stochastic orienteering* problem, in which we are given a budget B and a graph G=(V,E) with edge distances *d(u,v) *and a starting vertex *x.* Each vertex *v* represents a job with a deterministic reward and a random processing time, drawn from a known distribution.

Thursday, September 22, 2022 11:30 AM EDT

**Title:** Graphical Designs and Gale Duality

Monday, September 19, 2022 11:30 AM EDT

**Title:** Essential Covers of the Cube by Hyperplanes

Speaker: | Igor Araujo |

Affiliation: | University of Illinois Urbana-Champaign |

Location: | contact Sabrina Lato for Zoom link |

**Abstract:** An essential cover of the vertices of the n-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant, and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with $\lceil \frac{n}{2} \rceil + 1$ hyperplanes and showed that $\Omega(\sqrt{n})$ hyperplanes are required.

Friday, September 16, 2022 3:30 PM EDT

**Title:** Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

Speaker: | Lap Chi Lau |

Affiliation: | University of Waterloo |

Location: | MC 5501 |

**Abstract: **

The classical Cheeger's inequality relates the edge conductance $\phi$ of a graph and the second smallest eigenvalue $\lambda_2$ of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality $\psi^2 / \log |V| \lesssim \lambda_2^* \lesssim \psi$ connecting the vertex expansion $\psi$ of a graph $G=(V,E)$ and the maximum reweighted second smallest eigenvalue $\lambda_2^*$ of the Laplacian matrix. In this work, we first improve their result to $\psi^2 / \log d \lesssim \lambda_2^* \lesssim \psi$ where $d$ is the maximum degree in $G$, which is optimal assuming the small-set expansion conjecture. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti.

Friday, September 16, 2022 1:00 PM EDT

**Title:** Stochastic Probing with Applications

Speaker: | David Kalichman |

Affiliation: | University of Waterloo |

Location: | MC 6029 or contact Rian Neogi for Zoom link |

**Abstract:** We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active.

Monday, September 12, 2022 8:00 PM EDT

**Title:** On sesqui-regular graphs with fixed smallest eigenvalue

Speaker: | Qianqian Yang |

Affiliation: | Shanghai University |

Location: | Contact Sabrina Lato for Zoom link |

**Abstract: **Let λ ≥ 2 be an integer. For strongly regular graphs with parameters (v, k, a, c) and fixed smallest eigenvalue −λ, Neumaier gave two bounds on c by using algebraic property of strongly regular graphs. Subsequently, we studied a new class of regular graphs called sesqui-regular graphs, which contains strongly regular graphs as a subclass, and proved that for a given sesqui-regular graph with parameters (v, k, c) and smallest eigenvalue −λ, if k is very large, then either c ≤ λ² (λ − 1) or v − k − 1 ≤ (λ−1)²/4 + 1. This is joint work with Jack Koolen, Brhane Gebremichel and Jae Young Yang

Friday, September 9, 2022 1:00 PM EDT

**Title:** Conditional Value-at-Risk

Speaker: | Nathan Benedetto |

Affiliation: | University of Waterloo |

Location: | MC 6029 or contact Rian Neogi for the Zoom link |

**Abstract: **The mean and variance of a probability distribution may not reflect what one wants from a scenario involving uncertainty.In particular, such measures fall short of expressing risk in a way suitable for financial and similar applications.

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 our Office of Indigenous Relations.