Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Thursday, November 30, 2023 2:00 PM EST
Title: Polarization operators in superspace
| Speaker: | Kelvin Chan |
| Affiliation: | York University |
| Location: | MC 6029 |
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.
Abstract: The classic coinvariant space is a graded representation of the symmetric group with deep connections to permutation statistics and Hall-Littlewood polynomials. Its generalization, the diagonal harmonics, has a rich connection to Macdonald polynomials and the q,t-Catalan numbers. In this talk, we consider the variant of the classical coinvariant story in the superspace. We briefly survey its connections and recent developments. We introduce polarization operators and discuss a new basis for its alternating component. We also discuss a folklore on cocharge and propose a basis for the super harmonics.
Friday, December 1, 2023 1:00 PM EST
Title: Sublinear Regret 101
| Speaker: | Nathan Benedetto Proenca |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: The purpose of this talk is to look at specific algorithms for online convex optimization attaining sublinear regret. In this way, we can get more familiar with the online learning setup and with the ingredients necessary to attain sublinear regret.
Friday, December 1, 2023 3:30 PM EST
Title: Wires, bits, and the cost of sorting
| Speaker: | Samuel Jaques |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: How hard is it to sort a list of n integers? A basic course on algorithms says it's O(n log n) time, but what if the list is enormous - so big you would need to cover the surface of the moon just to store it?
Monday, December 4, 2023 11:30 AM EST
Title: A threshold for fractional Sudoku completion
| Speaker: | Peter Dukes |
| Affiliation: | University of Victoria |
| Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: The popular puzzle game Sudoku presents a player with a 9-by-9 grid having some numbers filled in a few of the cells. The player must finish filling in numbers from 1 to 9 so that every row, column, and 3-by-3 box contains each of these numbers exactly once. We can extend Sudoku so that the boxes are $h$-by-$w$, and the overall array is $n$-by-$n$, where $n=hw$. The puzzle is now similar to completing a latin square of order n, except of course that Sudoku has an additional box condition.
Thursday, December 7, 2023 3:00 PM EST
Title: The Container method for Enumerating Triangle-free graphs
| Speaker: | Amitha Vallapuram |
| Affiliation: | University of Waterloo |
| Location: | MC 5417 |
Abstract: The container method is a tool for bounding the number of independent sets in graphs and can be generalized to hypergraphs. It utilizes the observation that independent sets are found in clusters or “containers” within the graph. One application of this method is to bound the number of finite objects with some forbidden substructure. For example, we can bound the number of graphs on N vertices that do not contain K3 as a subgraph, that is, the number of Triangle-free graphs on N vertices. We will take a look at finding this bound using the container method.
Friday, December 8, 2023 3:30 PM EST
Title: Nash-Williams Orientation for Infinite Graphs
| Speaker: | Amena Assem Abd-AlQader Mahmoud |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: Nash-Williams proved in 1960 that an edge-connectivity of 2k is sufficient for a finite graph to admit a k-arc-connected orientation and conjectured that the same holds for infinite graphs. We show that the conjecture is true for locally finite graphs with countably many ends.
This is joint work with Max Pitz and Marcel Koloschin.
Friday, December 15, 2023 3:30 PM EST
Title: Online edge colouring
| Speaker: | David Wajc |
| Affiliation: | Technion — Israel Institute of Technology |
| Location: | MC 5501 |
Abstract: Vizing's Theorem provides an algorithm that edge colors any graph of maximum degree Δ can be edge-colored using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime.