#### 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, July 29, 2022 3:30 PM EDT

Title: Non-realizability of polytopes via linear programming

Speaker: | Amy Wiebe |

Affiliation: | UBC Okanagan |

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

Abstract: A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. In specific instances, answering the question in the negative is often done via “final polynomials” introduced by Bokowski and Sturmfels. This method involves finding a polynomial which, based on the structure of a polytope if realizable, must be simultaneously zero and positive, a clear contradiction.

Friday, July 29, 2022 1:00 PM EDT

**Title:** Stochastic Load Balancing on Unrelated Machines

Speaker: | Rian Neogi |

Affiliation: | University of Waterloo |

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

**Abstract: **We will take a look at the stochastic load balancing problem. The goal is to assign tasks to machines, so that the maximum amount of time taken by any machine to complete all its assigned tasks is minimized. The stochastic twist to this problem is that now the time required to complete each task is a random variable sampled from some known distribution. For the stochastic version, we need to minimize the maximum time taken by any machine in expectation. We will look at a constant factor approximation algorithm for this problem that appeared in a recent paper by Gupta, Kumar, Nagarajan and Shen.

Thursday, July 28, 2022 1:00 PM EDT

**Title:** Thresholds

Speaker: | Jinyoung Park |

Affiliation: | Standford University |

Location: | Please contact Logan Crew for the Zoom link |

**Abstract: **Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.

Friday, July 22, 2022 3:30 PM EDT

**Title:** Strongly regular graphs with a regular point

Speaker: | Krystal Guo |

Affiliation: | University of Amsterdam, Korteweg-de Vries Institute |

Location | MC 5501 or please contact Melissa Cambridge for the Zoom link |

**Abstract:** Arising from Hoffman and Singleton's study of Moore graphs, strongly regular graphs play an important role in algebraic graph theory. Strongly regular graphs can be construct from geometric objects, such as generalized quadrangles and certain geometric properties, such as having a regular point, can be studied in the context of graphs.

Friday, July 22, 2022 1:00 PM EDT

**Title:** Data-Driven Chance Constrained Programs over Wasserstein Balls

Speaker: | Matheus Ota |

Affiliation: | University of Waterloo |

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

**Abstract: **In many real-world applications, precise problem data is not available to the decision maker. One way to handle this uncertainty is by using chance-constraints, where the probability that at least one constraint is violated is bounded above by some parameter. However, such an approach assumes that the decision maker has access to the true probability distribution which governs the data behavior.

Tuesday, July 19, 2022 2:30 PM EDT

**Title:** High-Rank Matroids and Unavoidable Flats

Speaker: | Matt Kroeker |

Affiliation: | University of Waterloo |

Location: | MC 5417 |

**Abstract: **We discuss a variety of questions and results pertaining to conjectures of Geelen from 2021 on the unavoidable flats in matroids of sufficiently high rank. We will also explore the differences in how such questions are posed for various classes of matroids, why such differences are necessary, and how they could potentially be reconciled. A result for the class of binary matroids and an outline of its proof will be discussed in detail. Joint work with Jim Geelen.

Monday, July 18, 2022 11:30 AM EDT

**Title: **New Characterizations of Distance-Biregular Graphs

Speaker: | Sabrina Lato |

Affiliation: | University of Waterloo |

Location: | please contact Sabrina Lato for Zoom link |

Abstract: Fiol, Garriga, and Yebra introduced the notion of pseudo-distance-regular vertices, and were able to use this notion to come up with a characterization of when a graph is distance-regular. Subsequently, Fiol and Garriga were able to use pseudo-distance-regular vertices and a bound on the excess of a vertex to come up with another characterization of distance-regular graphs. We will present an overview of their results, as well as recent extensions to distance-biregular graphs.

Friday, July 15, 2022 3:30 PM EDT

**Title:** Positivity and sums of squares in products of free algebras

Speaker: | William Slofstra |

Affiliation: | University of Waterloo |

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

**Abstract: **A noncommutative polynomial is said to be positive relative to some constraints if plugging matrices (or more generally, operators on a Hilbert space) satisfying the constraints into the polynomial always yields a positive operator. It is a natural problem to determine whether or not a given polynomial is positive, and if it is, to find some certificate of positivity. This problem is closely connected with noncommutative polynomial optimization, where we want to find matrices or operators that maximize the operator norm of some polynomial, subject to the constraint that some other polynomials in the operators are positive or vanish. When the algebra cut out by the constraints is a free algebra, free group algebra, or similar algebra, it's well-known that a polynomial is positive on operators satisfying the constraints if and only if it's a sum of Hermitian squares in the algebra.

Friday, July 15, 2022 1:00 PM EDT

**Title:** Stochastic Optimization

Speaker: | Ricardo Fukaswaw |

Affiliation: | University of Waterloo |

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

Abstract: While deterministic optimization problems are very useful in practice, often times the assumption that all data is known in advance does not hold true. One possible way to relax this assumption is to assume that the data depends on random variables.

Thursday, July 14, 2022 1:00 PM EDT

**Title:** An identity in the group algebra of the symmetric group

Speaker: | Kevin Purbhoo |

Affiliation: | University of Waterloo |

Location: | MC 5479, contact Olya Mandelshtam for Zoom link |

**Abstract:** Come with me on a magical journey into the mysterious world of inverse Wronskians.

Tuesday, July 12, 2022 2:30 PM EDT

**Title:** The *k*-independence number of graph products

Speaker: | Hidde Koerts |

Affiliation: | University of Waterloo |

Location: | MC 5417 |

**Abstract:** The *k*-independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than *k*, generalizing the standard independence number. In this talk, I will discuss well-known sharp bounds on the independence number of graph products, and extend some of these bounds to the *k*-independence number. Specifically, we will cover the Cartesian, tensor, strong, and lexicographic products.

Joint work with Aida Abiad.

Monday, July 11, 2022 11:30 AM EDT

**Title:** Strong Cospectrality in Trees

Friday, July 8, 2022 3:30 PM EDT

**Title: **3-colouring via flows

Speaker: | Ben Moore |

Affiliation: | Charles University |

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

**Abstract: **I'll show a technique to colour graphs on surfaces using max-flow min-cut.

Friday, July 8, 2022 1:00 PM EDT

**Title: **Stochastic Optimization

Speaker: | Ricardo Fukasawa |

Affiliation: | University of Waterloo |

Location: | MC 6029 |

**Abstract: **While deterministic optimization problems are very useful in practice, often times the assumption that all data is known in advance does not hold true. One possible way to relax this assumption is to assume that the data depends on random variables. This assumption leads to stochastic optimization problems.

Thursday, July 7, 2022 1:00 PM EDT

**Title:** Box-ball systems, RSK, and Motzkin paths

Speaker: | Emily Gunawan |

Affiliation: | University of Oklahoma |

Location: | MC 5479, please contact Olya Mandelshtam for Zoom link. |

**Abstract:** A box-ball system (BBS) is a discrete dynamical system whose dynamics come from the balls jumping according to certain rules. A permutation on n objects gives a BBS state by assigning its one-line notation to n consecutive boxes. After a finite number of steps, a box-ball system will reach a steady state. From any steady state, we can construct a tableau called the soliton decomposition of the box-ball system.

Tuesday, July 5, 2022 2:30 PM EDT

**Title**: Bounded treewidth in hereditary graph classes

Speaker: | Sepehr Hajebi |

Affiliation: | University of Waterloo |

Location: | MC 5417 |

**Abstract: **A highlight of the superb graph minors project of Robertson and Seymour is their so-called Grid Theorem: a minor-closed class of graphs has bounded treewidth if and only it does not contain all planar graphs. Which induced-subgraph-closed graph classes have bounded treewidth?

Monday, July 4, 2022 11:30 AM EDT

**Title:** Spectral Turan Problems on trees and even cycles

Speaker: | Dheer Noal |

Affiliation: | University of Delaware |

Zoom: | Please contact Sabrina Lato for Zoom link |

**Abstract: **In this talk, we discuss some recent progress with the spectral analogue of a few Turán problems: Instead of maximizing the number of edges, our objective is to maximize the spectral radius of the adjacency matrices of graphs not containing some subgraphs.

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.