Events by month

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.

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? 

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.

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.

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.

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.

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

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.

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.

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.

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.

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.