## University COVID-19 update

### Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

# Events - 2021

Thursday, March 25, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - Colleen Robichaux

Title: An Efficient Algorithm for Deciding the Vanishing of Schubert Polynomial Coefficients

 Speaker: Colleen Robichaux Affiliation: University of Illinois at Urbana-Champaign Zoom: Contact Karen Yeats

Abstract:

Schubert polynomials form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. The vanishing problem for Schubert polynomials asks if a coefficient of a Schubert polynomial is zero. We give a tableau criterion to solve this problem, from which we deduce the first polynomial time algorithm. These results are obtained from new characterizations of the Schubitope, a generalization of the permutahedron defined for any subset of the n x n grid. In contrast, we show that computing these coefficients explicitly is #P-complete. This is joint work with Anshul Adve and Alexander Yong.

Friday, March 12, 2021 — 3:30 PM EST

## Tutte Colloquium - Bill Cook

Title: An approximate solution to a 2,079,471-point traveling salesman problem

 Speaker: Bill Cook Affliation: University of Waterloo Zoom: Please email Emma Watson

Abstract:

Together with Keld Helsguan, we have found a TSP tour through the 3D positions of 2,079,471 stars. We discuss how linear programming allows us to prove the tour is at most a factor of 0.0000074 longer than an optimal solution. The talk will focus on the use of minimum cuts and GF(2) linear systems, to drive the cutting-plane method towards strong LP relaxations.

Thursday, March 11, 2021 — 1:00 PM EST

## Algebraic Combinatorics Seminar - Karen Yeats

Title: Equivalences of Wilson loop diagrams

 Speaker: Karen Yeats Affiliation: University of Waterloo Zoom: Contact Karen Yeats

Abstract:

I will talk about Wilson loop diagrams, explain a bit about what they are, and some of the combinatorial questions that come out of them, with a focus on when they are equivalent.  This is joint work with Susama Agarwala and Zee Fryer.

Monday, March 8, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Joy Morris

Title: Lexicographic products, wreath products, and generalisations

 Speaker: Joy Morris Affiliation: University of Lethbridge Zoom: Contact Soffia Arnadottir

Abstract:

I will present a history and overview of some of the work that has been done on the lexicographic product of graphs, and related generalisations. The focus of my talk will be on the automorphism groups of such graphs, and the relationship to the wreath product of permutation groups.

Friday, March 5, 2021 — 3:30 PM EST

## Tutte Colloquium -Debbie Leung

Title: The embezzlement of entanglement and its applications

 Speaker: Debbie Leung Affliation: University of Waterloo Zoom: Please email Emma Watson

Abstract:

Embezzlement of entanglement is the (impossible) task of producing an entangled state from a product state via a local change of basis, when a suitable *catalytic* entangled state is available.

The possibility to approximate this task was first observed by van Dam and Hayden in 2002.  Since then, the phenomenon is found to play crucial roles in many aspects of quantum information theory.  In this talk, we will discuss aspects of embezzlement and some applications (such as why quantum correlations do not form a closed set, and why there are nonlocal games that cannot be played optimally with a finite amount of entanglement, and why additive quantities cannot be more than asymptotically continuous).

Thursday, March 4, 2021 — 4:00 PM EST

## C&O + PMath Joint Colloquium: Lukas Nabergall

Title: The Erdos-Szekeres theorem

 Speaker: Lukas Nabergall Affiliation: University of Waterloo Zoom: Contact Maxwell Levit

Abstract:

What lies at the intersection of combinatorial geometry, graph theory, order theory, analysis, and statistics? Why, only one of the most beautiful theorems you may have never heard of. Let me take you on a journey from early 20th century Budapest through to the heights of modern mathematics and show you why this classic result of Erdos and Szekeres is worth adding to your mathematical repertoire. Along the way we'll even see a proof so good it must come from The Book.

Thursday, March 4, 2021 — 1:00 PM EST

## Algebraic Combinatorics Seminar - Ralph Kaufmann

Title: Graphs and combinatorics with a relationship to algebra, geometry and physics

 Speaker: Ralph Kaufmann Affiliation: Purdue Zoom: Contact Karen Yeats

Abstract:

Several algebraic and geometric structures are most naturally encoded via graphs. These include restrictions, such as trees, and decorations, such as planar graphs, ribbon graphs, bi-partite graphs (aka. hypergraphs), directed versions, etc. Particularly nice properties satisfy some kind of hereditary condition. This affords a dual perspective. Either as (nested) subsets and decomposition, or as composition, gluing locally. Both views relate to category theory, algebra, and combinatorics in terms of finite sets, cospans etc. We will give examples of these phenomena and provide a general background.

Monday, March 1, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Hamed Karami

Title: Perfect Colorings of the Generalized Petersen Graphs

 Speaker: Hamed Karami Affiliation: Iran University of Science and Technology Zoom: Contact Soffia Arnadottir

Abstract:

For a graph G and an integer m, a mapping T:V(G) -> {1,...,m} is called a perfect m-coloring with matrix A=(a_ij), i,j \in {1,...,m}, if it is surjective, and for all i,j, for every vertex of color i, the number of its neighbors of color j is equal to a_ij. There is another term for this concept in literature as "equitable partition". In this talk, we present some important results about enumerating parameter matrices of all perfect 2-colorings and perfect 3-colorings of generalized Petersen graphs GP(n,k).

Friday, February 26, 2021 — 3:30 PM EST

## Tutte Colloquium - Robert Morris

Title: Flat Littlewood Polynomials Exist

 Speaker: Robert Morris Affliation: IMPA (Instituto de Matemática Pura e Aplicada) Zoom: Please email Emma Watson

Abstract:

In a Littlewood polynomial, all coefficients are either 1 or -1. Littlewood proved many beautiful theorems about these polynomials over his long life, and in his 1968 monograph he stated several influential conjectures about them. One of the most famous of these was inspired by a question of Erdos, who asked in 1957 whether there exist "flat" Littlewood polynomials of degree n, that is, with |P(z)| of order n^{1/2} for all (complex) z with |z| = 1.

Thursday, February 25, 2021 — 1:00 PM EST

## Algebraic Combinatorics Seminar - Nick Loehr

Title: Chain decompositions for q,t-Catalan numbers

 Speaker: Nick Loehr Affiliation: Virginia Tech Zoom: Contact Karen Yeats

Abstract:

The q,t-Catalan numbers Cat_n(q,t) are polynomials in q and t that reduce to the ordinary Catalan numbers when q=t=1. These polynomials have important connections to representation theory, algebraic geometry, and symmetric functions. Work of Garsia, Haglund, and Haiman has given us combinatorial formulas for Cat_n(q,t) as sums of Dyck vectors weighted by area and dinv. This talk narrates our ongoing quest for a bijective proof of the notorious symmetry property Cat_n(q,t)=Cat_n(t,q).

Monday, February 22, 2021 — 6:00 PM EST

## Algebraic Graph Theory Seminar - Gordon Royle

*Note different start time

Title: Real Chromatic Roots of Graphs

 Speaker: Gordon Royle Affiliation: The University of Western Australia Zoom: Contact Soffia Arnadottir

Abstract:

In February 1988, I arrived at C&O Waterloo for a postdoc with the late Ron Read. He handed me a paper by Beraha, Kahane and Weiss, and told me to apply it to determining the location of the complex roots of chromatic polynomials.  I’ve returned to the topic every few years since then, with varying degrees of success---some positive results, but still many open problems and conjectures remain.

Friday, February 12, 2021 — 3:30 PM EST

## Tutte Colloquium - Robert Hildebrand

Title: Mixed Integer Programming - Strength of adding integer variables

 Speaker: Robert Hildebrand Affliation: Virginia Tech Zoom: Please email Emma Watson

Abstract:

Mixed Integer Programming is the problem of optimizing a multi-variate function over some domain constraints where some variables are required to take integer values. From a complexity-theoretic perspective,  problems with fewer integer variables are easier to solve. However, this is not always the case in practice.  We will discuss how performance can be improved when adding integer variables in the context of cutting planes and branch and bound. We will compare several frameworks for doing so in both the context of converting lifting integer and continuous variables to more variables.  We will conclude with recent work on mixed-integer quadratic programming and mention some computational results.

Thursday, February 11, 2021 — 1:00 PM EST

## Algebraic Combinatorics Seminar - Julien Courtiel

Title: Solving Prellberg and Mortimer's conjecture - bijection(s)
between Motzkin paths and triangular walks

 Speaker: Julien Courtiel Affiliation: Université de Caen Zoom: Contact Karen Yeats

Abstract:

In these difficult times, what we need to feel better is some colorful and elegant bijections.

This talk introduces the work we did with Andrew Elvey-Price (Tours, France) and Irène Marcovici (Nancy, France). Together we answered an open question from Mortimer and Prellberg, asking for a bijection between a family of walks inside a bounded triangular domain (think about a large equilateral triangle subdivided in several smaller equilateral triangles) and the famous Motzkin paths, but which have bounded height.

Monday, February 8, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Mark Kempton

Title: Cospectral Vertices and Isospectral Reductions

 Speaker: Mark Kempton Affiliation: Brigham Young University Zoom: Contact Soffia Arnadottir

Abstract:

Understanding cospectral vertices in graphs is fundamental to understanding what the spectrum of the adjacency matrix can tell us about a graph.  Furthermore, cospectral vertices are necessary in constructions of graphs exhibiting perfect quantum state transfer.  I will talk about how to recognize cospectral vertices via a tool from network dynamics: the isospectral reduction of a graph.  I will explore possible ways of getting new constructions of cospectral vertices by looking at isospectral reductions.

Friday, February 5, 2021 — 3:30 PM EST

## Tutte Colloquium - Elchanan Mossel

Title: Probabilistic Aspects of Voting, Intransitivity, and Manipulation

 Speaker: Elchanan Mossel Affliation: MIT Mathematics Zoom: Please email Emma Watson

Abstract:

Marquis de Condorcet, a French philosopher, mathematician, and political scientist, studied mathematical aspects of voting in the eighteenth century. Condorcet was interested in studying voting rules as procedures for aggregating noisy signals and in the paradoxical nature of ranking  3 or more alternatives. We will begin with a quick survey of some of the main mathematical models, tools, and results in this theory and discuss some recent progress in the area.

Thursday, February 4, 2021 — 1:00 PM EST

## Algebraic Combinatorics Seminar - Jessica Striker

Title: Promotion and rowmotion – an ocean of notions

 Speaker: Jessica Striker Affiliation: North Dakota State University Zoom: Contact Karen Yeats

Abstract:

Dynamical Algebraic Combinatorics studies objects important in algebraic combinatorics through the lens of dynamical actions. In this talk, we give a flavor of this field by investigating ever more general domains in which the actions of promotion on tableaux (or tableaux-like objects) and rowmotion on order ideals (or generalizations of order ideals) correspond. This is based on joint works with J. Bernstein, K. Dilks, O. Pechenik, C. Vorland, and N. Williams.

Friday, January 29, 2021 — 3:30 PM EST

## Tutte Colloquium - Michael Naehrig

Title: Finding twin smooth integers for isogeny-based cryptography

 Speaker: Michael Naehrig Affliation: Microsoft Research Zoom: Please email Emma Watson

Abstract:

Efficient and secure instantiations of cryptographic protocols require careful parameter selection. For the isogeny-based cryptographic protocol B-SIDH, a variant of the Supersingular-Isogeny Diffie Hellman (SIDH) key exchange, one needs to find two consecutive B-smooth integers of cryptographic size such that their sum is prime. The smaller the smoothness bound B is, the more efficient the protocol becomes. This talk discusses a sieving algorithm to find such twin smooth integers that uses solutions to the Prouhet-Tarry-Escott problem.

Thursday, January 28, 2021 — 1:00 PM EST

## Algebraic Combinatorics Seminar - Olya Mandelshtam

Title: The multispecies TAZRP and modified Macdonald polynomials

 Speaker: Olya Mandelshtam Affiliation: University of Waterloo Zoom: Contact Karen Yeats

Abstract:

Recently, a formula for the symmetric Macdonald polynomials $P_{\lambda}(X;q,t)$ was given in terms of objects called multiline queues, which also compute probabilities of a statistical mechanics model called the multispecies asymmetric simple exclusion process (ASEP) on a ring. It is natural to ask whether the modified Macdonald polynomials $\widetilde{H}_{\lambda}(X;q,t)$ can be obtained using a combinatorial gadget for some other statistical mechanics model.

Monday, January 25, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Chris Godsil

Title: The Matchings Polynomial

 Speaker: Chris Godsil Affiliation: University of Waterloo Zoom: Contact Soffia Arnadottir

Abstract:

A $k$-matching in a graph is a matching of size $k$, and $p(X,k)$ denotes the number of $k$-matchings in $X$.

The matching polynomial of a graph is a form of generating function for the sequence $(p(X,k))_{k\ge0}$.

If is closely related to the characteristic polynomial of a graph. I will discuss some of the many interesting properties of this polynomial, and some of the related open problems.

Friday, January 22, 2021 — 3:30 PM EST

## Tutte Colloquium - David Gosset

Title: Fast simulation of planar Clifford circuits

 Speaker: David Gosset Aflliation: University of Waterloo YouTube Link: https://youtu.be/LjmjiEPTSNo

Abstract:

Clifford circuits are a special family of quantum circuits that can be simulated on a classical computer in polynomial time using linear algebra. Recent work has shown that Clifford circuits composed of nearest-neighbor gates in planar geometries can solve certain linear algebra problems provably faster --as measured by circuit depth-- than classical computers.

Thursday, January 21, 2021 — 1:30 PM EST

## Algebraic Combinatorics Seminar - Jason Bell

Title: The growth of groups and algebras

 Speaker: Jason Bell Affiliation: University of Waterloo Zoom: Contact Karen Yeats

Abstract:

We give an overview of the theory of growth functions for associative algebras and explain their significance when trying to understand algebras from a combinatorial point of view.  We then give a classification for which functions can occur as the growth function of a finitely generated associative algebra up to asymptotic equivalence. This is joint work with Efim Zelmanov.

Monday, January 18, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Shaun Fallat

Title: Various Maximum Nullities Associated with a Graph

 Speaker: Shaun Fallat Affiliation: University of Regina Zoom: Contact Soffia Arnadottir

Abstract:

Given a graph, we associate a collection of (typically symmetric) matrices S whose pattern of non-zero entries off of the main diagonal respects the edges in the graph. To this set, we let M denote the maximum possible nullity over all matrices in S. Depending on the choice of the set S, and the family of graphs considered, the parameter M often corresponds to an interesting combinatorial characteristic (planarity, connectivity, coverings, etc.) of the underlying graph.

Friday, January 15, 2021 — 3:30 PM EST

## Tutte Colloquium: Anupam Gupta

Title: Finding and Counting k-cuts in Graphs

 Speaker: Anupam Gupta Affiliation: Carnegie Mellon University Zoom: Please email Emma Watson

Abstract:

For an undirected graph with edge weights, a k-cut is a set of edges whose deletion breaks the graph into at least k connected components. How fast can we find a minimum-weight k-cut? And how many minimum k-cuts can a graph have? The two problems are closely linked. In 1996 Karger and Stein showed how to find a minimum k-cut in approximately n^{2k-2} time; their proof also bounded the number of minimum k-cuts by n^{2k-2}, using the probabilistic method.

Thursday, January 14, 2021 — 1:00 PM EST

## Algebraic Combinatorics Seminar - Steve Melczer

Title: Analytic Combinatorics, Rigorous Numerics, and Uniqueness of Biomembranes

 Speaker: Steve Melczer Affiliation: University of Waterloo Zoom: Contact Karen Yeats

Abstract:

Since the invention of the compound microscope in the early seventeenth century, scientists have marvelled over red blood cells and their surprising shape. An influential model of Canham predicts the shapes of blood cells and similar biomembranes come from a variational problem minimizing the "bending energy" of these surfaces. Because observed (healthy) cells have the same shape in humans, it is natural to ask whether the model admits a unique solution. Here, we prove solution uniqueness for the genus one Canham problem.

Monday, January 11, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Whitney Drazen

Title: K-fractional revival and approximate K-fractional revival on path graphs

 Speaker: Whitney Drazen Affiliation: Northeastern University Zoom: Contact Soffia Arnadottir

Abstract:

A continuous-time quantum walk is a process on a network of quantum particles that is governed by the transition matrix U(t) = e^{-itA}, where is A is the adjacency matrix of the graph. The two-vertex phenomenon fractional revival occurs between vertices u and v at time t if the columns of U(t) corresponding to u and v are only supported on the rows indexed by those same two vertices. The well-studied perfect state transfer is a special case of this.

## Pages

### March 2021

S M T W T F S
28
2
3
6
7
9
10
13
14
15
16
17
18
19
20
21
22
23
24
26
27
28
29
30
31
1
2
3
1. 2021 (26)
1. March (8)
2. February (8)
3. January (10)
2. 2020 (119)
1. December (5)
2. November (12)
3. October (12)
4. September (12)
5. August (11)
6. July (17)
7. June (11)
8. May (6)
9. March (11)
10. February (11)
11. January (11)
3. 2019 (167)
4. 2018 (136)
5. 2017 (103)
6. 2016 (137)
7. 2015 (136)
8. 2014 (88)
9. 2013 (48)
10. 2012 (39)
11. 2011 (36)
12. 2010 (40)
13. 2009 (40)
14. 2008 (39)
15. 2007 (15)