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, May 29, 2023 2:30 PM EDT
Title: Chromatic Symmetric Functions: Combining Algebra and Graph Theory
| Speaker: | Logan Crew |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: The chromatic polynomial, enumerating the proper colorings of a graph by number of colors used, was created by Birkhoff in the early 1900s to study the then Four-Color Conjecture. In the 1990s, Stanley generalized this to a chromatic symmetric function, which further counts for each proper n-coloring how many times each of the n colors is used.
Monday, May 29, 2023 1:00 PM EDT
Title: Bounding the extended complexity of the stable set polytope on perfect graphs
| Speaker: | Gabriel Morete |
| Affiliation: | University of Waterloo |
| Room: | MC 6029 |
Abstract: This week we will study the extension complexity of the stable set polytope for perfect graphs. More than 40 years ago, Grötschel et al. gave an algorithm to find maximal weight stable sets on perfect graphs based on a compact semidefinite extension. However, whether there is a compact linear extension is still an open problem.
Monday, May 29, 2023 11:30 AM EDT
Title: Eigenvalues for stochastic matrices with a prescribed stationary distribution
| Speaker: | Steve Kirkland |
| Affiliation: | University of Manitoba |
| Location: | Please contact Sabrina Lato for Zoom link |
Abstract: A square nonnegative matrix T is called stochastic if all of its row sums are equal to 1. Under mild conditions, it turns out that there is a positive row vector w^T (called the stationary distribution for T) whose entries sum to 1 such that the powers of T converge to the outer product of w^T with the all-ones vector. Further, the nature of that convergence is governed by the eigenvalues of T.
In this talk we explore how the stationary distribution for a stochastic matrix exerts an influence on the corresponding eigenvalues.
Friday, May 26, 2023 3:30 PM EDT
Title: Breaking the Supersingular Isogeny Diffie-Hellman protocol
| Speaker: | Wouter Castryck |
| Affiliation: | KU Leuven |
| Location: | Please contact Eva Lee for Zoom link |
Abstract: Finding an explicit isogeny between two given isogenous elliptic curves over a finite field is considered a hard problem, even for quantum computers.
Friday, May 26, 2023 1:30 PM EDT
Title: Generalized Modular String Averaged Procedure and Its Applications to Iterative Methods
| Speaker: | Kay Barshad |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: A modular string averaging procedure (MSA, for short) for a finite number of operators was first introduced by Reich and Zalas in 2016. The MSA concept provides a flexible algorithmic framework for solving various feasibility problems such as common fixed point and convex feasibility problems.
Tuesday, May 23, 2023 2:30 PM EDT
Title: Bounded degree arboricity
| Speaker: | Ronan Wdowinski |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: For a multigraph $G$ together with a positive weight $f(v)$ on every vertex $v$, we study the problem of covering the edge set of $G$ by the minimum number of forests $F$ in which every vertex $v$ has degree at most $f(v)$ in $F$.
Friday, May 19, 2023 3:30 PM EDT
Title: Lorentzian polynomials
| Speaker: | Petter Brändén |
| Affiliation: | KTH Royal Institute of Technology |
| Location: | MC 5501 |
Abstract: Lorentzian polynomials on cones are intimately connected to Hodge theory, matroid theory and the geometry of zeros of polynomials.
Thursday, May 18, 2023 3:00 PM EDT
Title: Snake decomposition of lattice path matroids
| Speaker: | Jerónimo Valencia Porras |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: Lattice path matroids (LPMs) are positroids whose base polytopes have a nice decomposition. We provide a geometric perspective to this decomposition in terms of fences and their order polytopes, which correspond to a certain class of LPMs we call snakes.
Monday, May 15, 2023 2:30 PM EDT
Title: A brief introduction to lattice-based cryptography
| Speaker: | Douglas Stebila |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: A brief introduction to lattice-based cryptography, one of the leading candidates for building quantum-resistant cryptosystems.
Monday, May 15, 2023 1:00 PM EDT
Title: The matching polytope has exponential extension complexity
| Speaker: | Jacob Skitsko |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: This Friday we will build off of some previous results by looking at the paper “The matching polytope has exponential extension complexity” by Thomas Rothvoss! At the beginning of the semester, we saw that the matching (and TSP) polytopes cannot be expressed by a polynomial sized symmetric LP.
Monday, May 15, 2023 11:30 AM EDT
Title: Orthogonal basis of eigenvectors for the Johnson and Kneser graphs
| Speaker: | Yuval Filmus |
| Affiliation: | Technion |
| Location: | Please contact Sabrina Lato for Zoom link |
Abstract: The Johnson and Kneser graphs have the same eigenspaces. How explicitly can we describe these eigenspaces?
Monday, May 1, 2023 11:30 AM EDT
Title: On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme
| Speaker: | Sjanne Zeijlemaker |
| Affiliation: |
Eindhoven University of Technology |
| Location: | Please contact Sabrina Lato for Zoom link |
Abstract: Graph classes in the Johnson, Grassmann and Hamming association scheme have received a considerable amount of attention over the last decades. Although several (NP-hard) graph parameters have been investigated for these families, many remain unknown. In this talk, we establish the diameter of generalized Grassmann graphs, extending previous results for generalized Johnson graphs.