# Events - 2021

Monday, December 13, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Logan Crew

Title: A New Graph Polynomial from the Chromatic Symmetric Function

 Speaker: Logan Crew Affiliation: University of Waterloo Zoom: Contact Soffia Arnadottir

Abstract:

The chromatic symmetric function X_G of a graph generalizes the chromatic polynomial by distinguishing proper n-colourings by how many times each colour is used. Furthermore, many other natural graph polynomials also arise from specializations of X_G;

Monday, December 6, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Cristina Dalfó

Title: On the Laplacian spectra of token graphs

 Speaker: Cristina Dalfó Affiliation: Universitat de Lleida Zoom: Contact Soffia Arnadottir

Abstract:

We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph F_k(G)of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this talk, we give a relationship between the Laplacian spectra of any two token graphs of a given graph.

Friday, December 3, 2021 — 3:30 PM EST

## Tutte Colloquium - Minh Bui

Title: Warped Proximal Iterations for Multivariate Convex Minimization in Hilbert Spaces

 Speaker: Minh Bui Affiliation: University of Waterloo Zoom: Please email Emma Watson

Abstract:

We propose a multivariate convex minimization model which involves a mix of nonsmooth and smooth functions, as well as linear mixtures of the variables. This formulation captures a wide range of concrete scenarios in the literature. A limitation of existing methods is that they do not achieve full splitting of our problem in the sense that each function and linear operator is activated separately. To circumvent this issue, we propose a novel approach, called warped proximal iterations, for solving this problem.

Monday, November 29, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Peter Dukes

Title: Fractional decompositions and Latin square completion

 Speaker: Peter Dukes Affiliation: University of Victoria Zoom: Contact Soffia Arnadottir

Abstract:

It was shown recently by Delcourt and Postle that any sufficiently large graph $G$ of order $n$ with minimum degree at least $0.827n$ has a fractional triangle decomposition, i.e. an assignment of weights to the triangles in $G$ such that for every edge $e$, the total of all weights of triangles containing $e$ is exactly one.

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

## Tutte Colloquium - Ashwin Nayak

Title: Quantum Distributed Complexity of Graph Diameter and Set Disjointness

 Speaker: Ashwin Nayak Affiliation: University of Waterloo Zoom: Please email Emma Watson

Abstract:

In the Congest model, a network of p processors cooperate to solve some distributed task. Initially, each processor knows only its unique label, the labels of its neighbours, and a polynomial upper bound on p, the size of the network. The processors communicate with their neighbours in rounds. In each round, a processor may perform local (quantum) computation, and send a short message to each of its neighbours. How many rounds of communication are required for some processor to compute the diameter of the network?

Monday, November 22, 2021 — 11:30 AM EST

## Algebraic Graph Theory Seminar - Emily King

Title: Switching Equivalence on the Grassmannian

Abstract:

When constructing configurations of subspaces with desirable properties, one might ask if the configuration is indeed "new.''  It has been known for about 50 years that Gram matrices of equiangular vectors in real Euclidean space correspond to finite simple graphs via the Seidel adjacency matrix, and the collections of such vectors which span the same lines correspond to switching equivalence classes of graphs.

Friday, November 19, 2021 — 3:30 PM EST

## Tutte Colloquium - Steph van Willigenburg

Title: The (3+1)-free conjecture of chromatic symmetric functions

 Speaker: Steph van Willigenburg Affiliation: University of British Columbia Zoom: Please email Emma Watson

Abstract:

The chromatic symmetric function, dating from 1995, is a generalization of the chromatic polynomial. A famed conjecture on it, called the Stanley-Stembridge (3+1)-free conjecture, has been the focus of much research lately. In this talk we will be introduced to the chromatic symmetric function, the (3+1)-free conjecture, new cases and tools for resolving it, and answer another question of Stanley of whether the (3+1)-free conjecture can be widened. This talk requires no prior knowledge.

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

## Tutte Colloquium - Greg Zaverucha

Title: Shorter Zero-Knowledge Proofs from MPC

 Speaker: Greg Zaverucha Affiliation: Microsoft Research Zoom: Please email Emma Watson

Abstract:

In this talk I will review the MPC-in-the-head approach to constructing zero-knowledge proofs, then talk about some recent research results to make the proofs shorter.

In a zero-knowledge proof system, a prover wants to convince a verifier that they know a secret value, without revealing it. A common case involves a one-way function, where the prover wants to convince a verifier that they know a secret input corresponding to a public output.

Friday, November 5, 2021 — 3:30 PM EDT

## Tutte Colloquium - László Végh

Title: On complete classes of valuated matroids

 Speaker: László Végh Affiliation: London School of Economics Zoom: Please email Emma Watson

Abstract:

Valuated matroids were introduced by Dress and Wenzel in 1992. They are a central object in discrete convex analysis, and play important roles in other areas such as mathematical economics and tropical geometry. Finding a constructive characterization, i.e., showing that all valuated matroids can be derived from a simple class by some basic operations has been a natural question proposed in various contexts.

Monday, November 1, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Allen Herman

Title: The results of a search for small association schemes with noncyclotomic eigenvalues

 Speaker: Allen Herman Affiliation: University of Regina Zoom: Contact Soffia Arnadottir

Abstract:

Monday, October 25, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Hermie Monterde

Title: State transfer on graphs with twin vertices

 Speaker: Hermie Monterde Affiliation: University of Manitoba Zoom: Contact Soffia Arnadottir

Abstract:

In this talk, we discuss algebraic and spectral properties of graphs with twin vertices that are important in quantum state transfer. We give a characterization of strong cospectrality between twin vertices, and characterize some types of state transfer that occur between them.

Friday, October 22, 2021 — 3:30 PM EDT

## Tutte Colloquium - Ahmad Abdi

 Speaker: Ahmad Abdi Affiliation: London School of Economics Zoom: Please email Emma Watson

Abstract:

Most linear programming solvers use fixed-precision floating points to approximate the rational numbers. Though successful on most real-world instances, solvers sometimes run into serious issues when carrying out sequential floating-point arithmetic, due to compounded error terms. This practical limitation leads to the following theoretical problem:

Friday, October 8, 2021 — 3:30 PM EDT

## Tutte Colloquium - Sophie Spirkl

Title: Induced subgraphs and treewidth

 Speaker: Sophie Spirkl Affiliation: University of Waterloo Zoom: Please email Emma Watson

Abstract:

Treewidth, introduced by Robertson and Seymour in the graph minors series, is a fundamental measure of the complexity of a graph. While their results give an answer to the question, “what minors occur in graphs of large treewidth?,” the same question for induced subgraphs is still open. I will talk about some conjectures and recent results in this area.

Joint work with Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, Kristina Vuskovic.

Thursday, October 7, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - Shiliang Gao

Title: Newell-Littlewood numbers

 Speaker: Shiliang Gao Affiliation: University of Illinois at Urbana-Champaign Zoom: Contact Steve Melczer

Abstract:

The Newell-Littlewood numbers are defined in terms of the Littlewood-Richardson coefficients. Both arise as tensor product multiplicities for a classical Lie group. A. Klyachko connected eigenvalues of sums of Hermitian matrices to the saturated LR-cone and established defining linear inequalities.

Monday, October 4, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Miguel Angel Fiol Mora

Title: Four families of polynomials in spectral graph theory

 Speaker: Miguel Angel Fiol Mora Affiliation: Universitat Politècnica de Catalunya Zoom: Contact Soffia Arnadottir

Abstract:

In this talk we describe four families of polynomials related to the spectrum of a graph. First, some known main results involving such polynomials, such as the spectral excess theorem characterizing distance-regularity, are discussed. Second, some new results giving bounds for the $k$-independence number $\alpha_k$ of a graph are presented. In this context, we comment on some relationships between the inertia (Cvetkovi\`c) and ratio (Hoffman) bounds of $\alpha_k$.

Friday, October 1, 2021 — 3:30 PM EDT

## Tutte Colloquium - Stephen Jordan

Title: Quantum information science for combinatorial optimization

 Speaker: Stephen Jordan Affiliation: Microsoft Quantum & University of Maryland Zoom: Please email Emma Watson

Abstract:

Due to input-output bottlenecks, quantum computers are expected to be most applicable to problems for which the quantity of data specifying the instance is small but the computational cost of finding a solution is large. Aside from cryptanalysis and quantum simulation, combinatorial optimization provides some of the best candidates for problems of real-world impact fitting these criteria. Many of these problems are NP-hard and thus unlikely to be solvable on quantum computers with polynomial worst-case time complexity.

Thursday, September 30, 2021 — 1:00 PM EDT

## Algebraic Combinatorics Seminar - John Noel

Title: Forcing Quasirandomness in Permutations

 Speaker: John Noel Affiliation: University of Victoria Zoom: Contact Steve Melczer

Abstract:

A striking result in graph theory is that the property of a graph being quasirandom (i.e. resembling a random graph) is characterized by the number of edges and the number of 4-cycles being close to the expected number in a random graph. Král’ and Pikhurko (2013) proved an analogous result for permutations; i.e. that quasirandom permutations are characterized by the densities of all permutations of length 4.

Thursday, September 30, 2021 — 11:00 AM EDT

## Optimization: Theory, Algorithms, Applications Lecture Series (The Fields Institute) - Bissan Ghaddar

Title: Structured (In)Feasibility: Nonmonotone Operator Splitting in Nonlinear Spaces

 Speaker: Bissan Ghaddar Affiliation: Western University Zoom: Register through The Fields Institute

Abstract:

Several challenging optimization problems in power networks involve operational decisions, non-linear models of the underlying physics described by the network as well as uncertainty in the system parameters. However, these networks exhibit a nice structure. This talk provides an overview of approaches that combine recent advances in robust optimization and conic relaxations of polynomial optimization problems along with exploiting the structure of the underlying problem. These approaches are demonstrated on applications arising in power networks.

Thursday, September 30, 2021 — 10:00 AM EDT

## Optimization: Theory, Algorithms, Applications Lecture Series (The Fields Institute) - Miguel Anjos

Title: Semidefinite Optimization Approaches for Reactive Optimal Power Flow Problems

 Speaker: Miguel Anjos Affiliation: University of Edinburgh Zoom: Register through The Fields Institute

Abstract:

The Reactive Optimal Power Flow (ROPF) problem consists in computing an optimal power generation dispatch for an alternating current transmission network that respects power flow equations and operational constraints. Some means of voltage control are modelled in ROPF such as the possible activation of shunts, and these controls are modelled using discrete variables. The ROPF problem belongs to the class of nonconvex MINLPs, which are NP-hard problems. We consider semidefinite optimization approaches for solving ROPF problems and their integration into a branch-and-bound algorithm.

Monday, September 27, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Thomás Spier

Title: Graph Continued Fractions

 Speaker: Thomás Spier Affiliation: Matemática Pura e Aplicada (IMPA) Zoom: Contact Soffia Arnadottir

Abstract:

This talk is about a connection between matching polynomials and continued fractions. For the matching polynomials: we prove a refinement of a theorem by Ku and Wong, which extends the classical Gallai-Edmonds decomposition;

Friday, September 24, 2021 — 3:30 PM EDT

## Tutte Colloquium - Tibor Jager

Title: Tightly-Secure Digital Signatures

 Speaker: Tibor Jager Affiliation: University of Wuppertal, Germany Zoom: Please email Emma Watson

Abstract:

This talk will cover two recent results on tightly-secure digital signature schemes from PKC 2021 and ASIACRYPT 2021.

The first part will consider a strong multi-user security definition for signatures with adaptive corruptions of secret keys, discuss its applications, and the technical challenges of constructing signatures with tight security in this setting. Then we will show a quite simple and efficient construction, based on sequential OR-proofs.

Monday, September 20, 2021 — 11:03 AM EDT

## Algebraic Graph Theory Seminar - Kate Lorenzen

Title: Spectral Properties of the exponential distance matrix

 Speaker: Kate Lorenzen Affiliation: Linfield University Zoom: Contact Soffia Arnadottir

Abstract:

Given a graph $G$, the exponential distance matrix is defined entry-wise by letting the $(u,v)$-entry be $q^{dist(u,v)}$ where $dist(u,v)$ is the distance between the vertices $u$ and $v$ with the convention that if vertices are in different components, then $q^{dist(u,v)}=0$. We establish several properties of the characteristic polynomial (spectrum) for this matrix and the inertia of some graph families.

Friday, September 17, 2021 — 3:30 PM EDT

## Tutte Colloquium - Alex Pothen

Title: Approximation Algorithms for Matchings in Big Graphs

 Speaker: Alex Pothen Affiliation: Purdue University Zoom: Please email Emma Watson

Abstract:

Matchings in graphs are classical problems in combinatorial optimization and computer science, significant due to their theoretical importance and relevance to applications. Polynomial time algorithms for several variant matching problems with linear objective functions have been known for fifty years, with important contributions from Tutte, Edmonds, Cunningham, and Pulleyblank (all with Waterloo associations), and they are discussed in the textbook literature.

Monday, September 13, 2021 — 11:30 AM EDT

## Algebraic Graph Theory Seminar - Chris Godsil

Title: Tails and Chains

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

Abstract:

Physicists are interested in "graphs with tails"; these are constructed by choosing a graph X and a subset C of its vertices, then attaching a path of length n to each vertex in C. We ask what is the spectrum of such graph? What happen if n increases? We will see that the answer reduces to questions about the matrix

$M(\zeta) := (\zeta_\zeta^{-1})I - A -\zeta D$

where D is the diagonal 01-matrix with D_{i,i}=1 if i is in C.

Friday, September 10, 2021 — 3:30 PM EDT

## Tutte Colloquium - Jane Ye

Title: On solving bilevel programming problems

 Speaker: Jane Ye Affiliation: University of Victoria Zoom: Please email Emma Watson

Abstract:

A bilevel programming problem is a sequence of two optimization problems where the constraint region of the upper level problem is determined implicitly by the solution set to the lower level problem. It can be used to model a two-level hierarchical system where the two decision makers have different objectives and make their decisions on different levels of hierarchy. Recently more and more applications including those in machine learning have been modelled as bilevel optimization problems. In this talk, I will report some recent developments in optimality conditions and numerical algorithms for solving this class of very difficult optimization problems.

## Pages

### January 2021

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