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, November 30, 2020 — 11:30 AM EST
Title: Simple eigenvalues of graph
| Speaker: | Krystal Guo |
| Affiliation: | University of Amsterdam |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
If v is an eigenvector for eigenvalue λ of a graph X and α is an automorphism of X, then α(v) is also an eigenvector for λ. Thus it is rather exceptional for an eigenvalue of a vertex-transitive graph to be simple. We study cubic vertex-transitive graphs with a non-trivial simple eigenvalue, and discover remarkable connections to arc-transitivity, regular maps and Chebyshev polynomials.
Monday, November 23, 2020 — 11:30 AM EST
Title: Complexity Measures on the Symmetric Group and Beyond
| Speaker: | Nathan Lindzey |
| Affiliation: | CU Boulder |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
A classical result in complexity theory states that a degree-d Boolean function on the hypercube can be computed using a decision tree of depth poly(d). Conversely, a Boolean function computed by a decision tree of depth d has degree at most d. Thus degree and decision tree complexity are polynomially related. Many other complexity measures of Boolean functions on the hypercube are polynomially related to the degree (e.g., approximate degree, certificate complexity, block sensitivity), and last year Huang famously added sensitivity to the list. Can we prove similar results for Boolean functions on other combinatorial domains?
Friday, November 20, 2020 — 3:30 PM EST
Title: Beyond rank
| Speaker: | Jordan Ellenberg |
| Affiliation: | University of Wisconsin |
| Zoom: | Please email Emma Watson |
Abstract:
The notion of the rank of a matrix is one of the most fundamental in linear algebra. The analogues of this notion in multilinear algebra — e.g., what is the “rank” of an m x n x p array of numbers? — is much more mysterious, but it also has proven to be useful in a wide array of contexts. I will talk about some questions and answers in “higher rank” coming from complexity theory, data science, geometric combinatorics, additive number theory, and commutative algebra.
Thursday, November 19, 2020 — 1:00 PM EST
Title: Some new lemmas about polynomials with only real roots
| Speaker: | David Wagner |
| Affiliation: | University of Waterloo |
| Zoom: | Contact Karen Yeats |
Abstract:
Recent investigations in Ehrhart theory suggested some conjectures involving interlacing relations among polynomials with only real roots, and Veronese sections of them. Revisiting some old theorems, we find as corollaries some new lemmas which have been overlooked for a long time. One of these lemmas directly implies a strong form of the motivating conjecture. Similar applications of the other lemmas are anticipated. This is ongoing joint work with Christos Athanasiadis (U. Athens).
Monday, November 16, 2020 — 11:30 AM EST
Title: Fractional revival on graphs
| Speaker: | Xiaohong Zhang |
| Affiliation: | University of Waterloo |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
Let A be the adjacency matrix of a weighted graph, and let U(t)=exp(itA). If there is a time t such that U(t)e_a=\alpha e_a+\beta e_b, then we say there is fractional revival (FR) between a and b. For the special case when \alpha=0, we say there is perfect state transfer (PST) between vertices a and b. It is known that PST is monogamous (PST from a to b and PST from a to c implies b=c) and vertices a b are cospectral in this case. If \alpha\beta\neq 0, then there is proper fractional revival.
Friday, November 13, 2020 — 3:30 PM EST
Title: Sampling Under Symmetry
| Speaker: | Nisheeth Vishnoi |
| Affiliation: | Yale University |
| Zoom: | Please email Emma Watson |
Abstract:
Exponential densities on orbits of Lie groups such as the unitary group are endowed with surprisingly rich mathematical structure and. traditionally, arise in diverse areas of physics, random matrix theory, and statistics.
In this talk, we will discuss the computational properties of such distributions and also present new applications to quantum inference and differential privacy.
Thursday, November 12, 2020 — 1:00 PM EST
Title: Face enumeration and real-rootedness
| Speaker: | Christos Athanasiadis |
| Affiliation: | University of Athens |
| Zoom: | Contact Karen Yeats |
Abstract:
About fifteen years ago F. Brenti and V. Welker showed that the face enumerating polynomial of the barycentric subdivision of any Cohen-Macaulay simplicial complex has only real roots. It is natural to ask whether similar results hold when barycentric subdivision is replaced by more general types of triangulations, or when simplicial complexes are replaced by more general cell complexes.
Monday, November 9, 2020 — 8:00 PM EST
Title: Scaling limits for the Gibbs states on distance-regular graphs with classical parameters
| Speaker: | Hajime Tanaka |
| Affiliation: | Tohoku University |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
Limits of the normalized spectral distributions and other related probability distributions of families of graphs have been studied in the context of quantum probability theory as analogues of the central limit theorem. First I will review some of the previous work by Hora, Obata, and others, focusing on the case of distance-regular graphs, and emphasizing how the theory is related to the Terwilliger algebra.
Friday, November 6, 2020 — 3:30 PM EST
Title: Constructing broken SIDH parameters: a tale of De Feo, Jao, and Plut's serendipity
| Speaker: | Chloe Martindale |
| Affiliation: | University of Bristol |
| Zoom: | Please email Emma Watson |
Abstract:
This talk is motivated by analyzing the security of the cryptographic key exchange protocol SIDH (Supersingular Isogeny Diffie-Hellman), introduced by 2011 by De Feo, Jao, and Plut. We will first recall some mathematical background as well as the protocol itself. The 'keys' in this protocol are elliptic curves, which are typically described by equations in x and y of the form y^2 = x^3 + ax + b.
Thursday, November 5, 2020 — 1:00 PM EST
Title: Filtering Grassmannian cohomology via k-Schur functions
| Speakers: | Huda Ahmed and Yuanning Zhang |
| Affiliation: | New York University and UC Berkeley |
| Zoom: | Contact Karen Yeats |
Abstract:
This talk concerns the cohomology rings of complex Grassmannians. In 2003, Reiner and Tudose conjectured the form of the Hilbert series for certain subalgebras of these cohomology rings. We build on their work in two ways. First, we conjecture two natural bases for these subalgebras that would imply their conjecture using notions from the theory of k-Schur functions. Second we formulate an analogous conjecture for Lagrangian Grassmannians.
Joint work with Michael Feigen, Victor Reiner, and Ajmain Yamin.
Thursday, November 5, 2020 — 1:00 PM EST
Title: Packings of partial difference sets
| Speaker: | Jonathan Jedwab |
| Affiliation: | Simon Fraser University |
| Zoom: | Contact Karen Yeats |
Abstract:
Partial difference sets are highly structured group subsets that occur in various guises throughout design theory, finite geometry, coding theory, and graph theory. They admit only two possible nontrivial character sums and so are often studied using character theory.
Monday, November 2, 2020 — 11:30 AM EST
Title: Monogamy Violations in Perfect State Transfer
| Speakers: | Sabrina Lato & Christino Tamon |
| Affiliations: | University of Waterloo & Clarkson Unversity |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
Continuous-time quantum walks on a graph are defined using a Hermitian matrix associated to a graph. For a quantum walk on a graph using either the adjacency matrix or the Laplacian, there can be perfect state transfer from a vertex to at most one other vertex in the graph.