Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Friday, December 15, 2023 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - David Wajc

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.

Monday, January 8, 2024 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory - Alan Lew

Title: Eigenvalues of high dimensional Laplacian operators

Speaker: Alan Lew
Affiliation: Carnegie Melon University
Location: Please contact Sabrina Lato for Zoom link.

Abstract: A simplicial complex is a topological space built by gluing together simple building blocks (such as vertices, edges, triangles and their higher dimensional counterparts). Alternatively, we can define a simplicial complex combinatorially, as a family of finite sets that is closed under inclusion. In 1944, Eckmann introduced a class of high dimensional Laplacian operators acting on a simplicial complex. These operators generalize the Laplacian matrix of a graph (which can be seen as a 0-dimensional Laplacian), and are strongly related to the topology of the complex (and in particular, to its homology groups).

Monday, January 15, 2024 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory - Carolyn Reinhart

Title: The non-backtracking matrix

Speaker: Carolyn Reinhart
Affiliation: Swarthmore College
Location: Please contact Sabrina Lato for Zoom link.

Abstract: A non-backtracking walk in a graph is any traversal of the vertices of a graph such that no edge is immediately repeated. The non-backtracking matrix of a graph is indexed by the directed edges of the graph, and encodes if two edges can be traversed in succession. Since this matrix is not symmetric, the question of when the matrix is diagonalizable is of interest to those who study it. Equivalently, such graphs have a non-trivial Jordan block. In this talk, I will present an overview of the non-backtracking matrix, including its history and applications. Finally, I will present recent results about graphs with non-trivial Jordan blocks for the non-backtracking matrix from joint work with Kristin Heysse, Kate Lorenzen, and Xinyu Wu.

Monday, January 22, 2024 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory - Gabor Lippner

Title: Pretty Good Fractional Revival via Magnetic Fields - theory and examples

Speaker: Gabor Lippner
Affiliation: Northeastern University
Location: Please contact Sabrina Lato for Zoom link.

Abstract: I will discuss the notion of PGFR relative to a given subset of nodes of a graph. This is a generalization of the more standard (pretty good) fractional revival between 2 nodes. In the process, I will introduce the proper generalization of cospectrality to the fractional setting, and give the appropriate extensions of methods already in use for the 2-vertex case. These include the Kronecker condition and the field-trace method. I will conclude by giving various families of examples of PGFR in the presence of (transcendental) magnetic fields.

Thursday, January 25, 2024 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and Enumerative Combinatorics - Santiago Estupinan

Title: A new shifted Littlewood-Richardson rule

Speaker: Santiago Estupinan
Affiliation: University of Waterloo
Location: MC 5479

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.

Abstract: As Littlewood-Richardson rules compute linear representation theory of symmetric groups and cohomology of ordinary Grassmannians, shifted Littlewood-Richardson rules compute analogous projective representation theory of symmetric groups and cohomology of orthogonal Grassmannians. The first shifted Littlewood-Richardson rule is due to Stembridge (1989), building on a natural generalization by Sagan and Worley (1979/1984) of the jeu de taquin algorithm to shifted Young tableaux. We give a new shifted Littlewood-Richardson rule that requires consideration of fewer tableaux than Stembridge's rule and appears to involve an easier check on each. Our rule derives from applying old ideas of Lascoux and Schützenberger (1981) to the study of Haiman's mixed insertion (1989) and Serrano's shifted plactic monoid (2010). (Joint work with Oliver Pechenik).

Friday, January 26, 2024 12:00 pm - 1:30 pm EST (GMT -05:00)

C&O Reading Group - Rian Neogi

Title: Follow the Regularized Leader and Mirror Descent

Speaker: Rian Neogi
Affiliation: University of Waterloo
Location: MC 6029

Abstract: In previous talks, we have seen how the multiplicative weights method and gradient descent solve the regret minimization problem. In this talk we will go over a meta-algorithm called Follow the Regularized Leader (FTRL). We will show how FTRL generalizes both multiplicative weights and gradient descent. We will also talk about the Mirror Descent meta-algorithm, and show its equivalence with FTRL.

Thursday, February 1, 2024 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and Enumerative Combinatorics - Arad Nasiri

Title: Combinatorial Action in Causal Set Quantum Gravity

Speaker: Arad Nasiri
Affiliation: Imperial College London and Perimeter Institute
Location: MC 5479

Abstract: In this talk, I will first provide a brief overview of causal set theory, an approach to quantum gravity. This theory proposes that spacetime is fundamentally characterized by a partially ordered set (poset), in which the partial order represents causal relations and the number of elements signifies the volume of a spacetime manifold region. I will then discuss how efforts to find a discrete counterpart of the d'Alembertian operator on a poset led to the formulation of the causal set action S_BDG. This action is defined as a linear combination of the counts of various order intervals. Further analysis has shown that while KR posets are predominant in the number of posets of size n, the quantum dynamics imposed by S_BDG suppresses them for large n. Finally, I will propose a method to derive the combinatorial analogue of Einstein's field equations on posets.

Friday, February 2, 2024 12:00 pm - 1:00 pm EST (GMT -05:00)

C&O Reading Group - Rian Neogi

Title: Regret bounds for FTRL and Mirror Descent

Speaker: Rian Neogi
Affiliation: University of Waterloo
Location: MC 6029

Abstract: In the previous talk, I introduced FTRL and Mirror Descent and showed how they generalize two well-known algorithms of Multiplicative Weights and Gradient Descent. In this talk, I will show that FTRL and Mirror Descent are in fact equivalent in the sense that they produce the same sequence of predictions. Moreover, I will go over some regret bounds for these algorithms, that will generalize the regret bounds we get for multiplicative weights and gradient descent.

Monday, February 5, 2024 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory - Chris Godsil

Title: Laplacian State Transfer

Speaker: Chris Godsil
Affiliation: University of Waterloo
Location: Please contact Sabrina Lato for Zoom link.

Abstract: Let $X$ be a graph and let $E_1,\ldots,E_d$ be the spectral idempotents of its adjacency matrix. If $a$ and $b$ are vertices in $X$, they are \textsl{strongly cospectral} if $E_re_ae_a^TE_r = E_re_be_b^T$ for each $r$. This is a relation between the two density matrices $e_aa_a^T$ and $e_be_b^T$, and is a necessary condition for state transfer between pure states.

If $L$ is the Laplacian of a graph $X$ with $m$ edges, the matrix $(1/2m)L$ is positive semidefinite with trace one, thus it is a density matrix. We call it a \textsl{Laplacian state}. It is pure only if $X$ is an edge. We have been investigating transfer between Laplacian states in continuous quantum walks. We have extended the definition of strongly cospectral to this case, have obtained a number of results are about various forms of state transfer. My talk will be a report on this.

(This is joint work with Ada Chan, Qiuting Chen, Wanting Sun and Xiaohong Zhang.)

Tuesday, February 6, 2024 3:00 pm - 4:00 pm EST (GMT -05:00)

Graphs and Matroids - Peter Nelson

Title: Biased cliques

Speaker: Peter Nelson
Affiliation: University of Waterloo
Location: MC 5417

Abstract: A biased clique is a collection of cycles in a complete graph G so that no theta of G contains exactly two cycles in the collection. They have interesting connections to both matroids and groups; I will give a survey of some results on these objects.