#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Visit our COVID-19 information website to learn how Warriors protect Warriors.

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

Friday, October 9, 2020 — 3:30 PM EDT

**Title: **Generalization bounds for rational self-supervised learning algorithms

Speaker: | Boaz Barak |

Affiliation: | Harvard University |

Zoom: | Please email Emma Watson |

**Abstract:**

The generalization gap of a learning algorithm is the expected difference between its performance on the training data and its performance on fresh unseen test samples.Modern deep learning algorithms typically have large generalization gaps, as they use more parameters than the size of their training set. Moreover the best known rigorous bounds on their generalization gap are often vacuous.

Thursday, October 8, 2020 — 1:00 PM EDT

**Title:** Factorization problems in complex reflection groups

Speaker: | Alejandro Morales |

Affiliation: | University of Massachusetts Amherst |

Zoom: | Contact Karen Yeats |

**Abstract:**

The study of factorizations in the symmetric group is related to combinatorial objects like graphs embedded on surfaces and non-crossing partitions. We consider analogues for complex reflections groups of certain factorization problems of permutations first studied by Jackson, Schaeffer, Vassilieva and Bernardi.

Monday, October 5, 2020 — 11:30 AM EDT

**Title:** Efficient $(j,k)$-Domination

Speaker: | Brendan Rooney |

Affiliation: | Rochester Institute of Technology |

Zoom: | Contact Soffia Arnadottir |

**Abstract****:**

A function $f:V(G)\rightarrow\{0,\ldots,j\}$ is an efficient $(j,k)$-dominating function on $G$ if $\sum_{u\in N[v]}f(u)=k$ for all $v\in V(G)$ (here $N[v]=N(v)\cup\{v\}$ is the closed neighbourhood of $v$).

Friday, October 2, 2020 — 3:30 PM EDT

**Title: **Total Dual Integrality for Convex, Semidefinite and Extended Formulations

Speaker: | Levent Tuncel |

Affiliation: | University of Waterloo |

Zoom: | Please email Emma Watson |

**Abstract:**

Within the context of characterizations of exactness of convex relaxations of 0,1 integer programming problems, we present a notion of total dual integrality for Semidefinite Optimization Problems (SDPs), convex optimization problems and extended formulations of convex sets.

Monday, September 28, 2020 — 11:30 AM EDT

**Title: **Strongly cospectral vertices, Cayley graphs and other things

Speaker: | Soffia Arnadottir |

Affiliation: | University of Waterloo |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

In this talk we will look at a connection between the number of pairwise strongly cospectral vertices in a translation graph (a Cayley graph of an abelian group) and the multiplicities of its eigenvalues. We will use this connection to give an upper bound on the number of pairwise strongly cospectral vertices in cubelike graphs.

Friday, September 25, 2020 — 1:00 PM EDT

**Title: **Rota's Basis Conjecture holds asymptotically

Speaker: | Alexey Pokrovskiy |

Affiliation: | Birkbeck, University of London |

Zoom: | Please email Emma Watson |

**Abstract:**

Rota's Basis Conjecture is a well known problem, that states that for any collection of n bases in a rank n matroid, it is possible to decompose all the elements into n disjoint rainbow bases. Here an asymptotic version of this is will be discussed - that it is possible to find n − o(n) disjoint rainbow independent sets of size n − o(n).

Thursday, September 24, 2020 — 1:00 PM EDT

**Title:** Sign variations and descents

Speaker: | Aram Dermenjian |

Affiliation: | York University |

Zoom: | Contact Karen Yeats |

**Abstract:**

In this talk we consider a poset structure on projective sign vectors. We show that the order complex of this poset is partitionable and give an interpretation of the h-vector using type B descents of the type D Coxeter group.

Monday, September 21, 2020 — 11:30 AM EDT

**Title: **Leonard pairs, spin models, and distance-regular graphs

Speaker: | Paul Terwilliger |

Affiliation: | University of Wisconsin |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

A Leonard pair is an ordered pair of diagonalizable linear maps on a finite-dimensional vector space, that each act on an eigenbasis for the other one in an irreducible tridiagonal fashion. In this talk we consider a type of Leonard pair, said to have spin.

Friday, September 18, 2020 — 3:30 PM EDT

**Title: **Hard Combinatorial Problems, Doubly Nonnegative Relaxations, Facial

and Symmetry Reduction, and Alternating Direction Method of Multipliers

Speaker: | Henry Wolkowicz |

Affiliation: | University of Waterloo |

Zoom: | Please email Emma Watson |

**Abstract:**

Semi-definite programming, SDP, relaxations have proven to be extremely successful both in theory and practice for many hard combinatorial problems. This is particularly true for the Max-Cut problem, where problems of dimension in the thousands have been solved to optimality. In contrast, the quadratic assignment problem, QAP, is an NP-hard problem where dimensions bigger than $30$ are still considered hard. SDP and in particular, the doubly nonnegative, DNN, relaxation have been successful in providing strong upper and lower bounds, and even solving many instances to optimality.

Thursday, September 17, 2020 — 2:30 PM EDT

**Title:** Edge Deletion-Contraction in the Chromatic and Tutte Symmetric Functions

Speaker: | Logan Crew |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

We consider symmetric function analogues of the chromatic and Tutte polynomials on graphs whose vertices have positive integer weights. We show that in this setting these functions admit edge deletion-contraction relations akin to those of the corresponding polynomials, and we use these relations to give enumerative and/or inductive proofs of properties of these functions.

Monday, September 14, 2020 — 4:00 PM EDT

Researchers today build on the knowledge and discoveries made by those who have come before them. How can today’s researchers light the early pathways and curiosities for the research breakthroughs of the future? How can we demonstrate the impact and potential of the yet-to-be known? And, what if any, role does academia, industry, the Faculty of Mathematics, and Canada play in increasing the discovery journey to these new frontiers?

Monday, September 14, 2020 — 3:00 PM EDT

**Title:** Foundations of Matroids without Large Uniform Minors, Part 2

Speaker: | Oliver Lorscheid |

Affiliation: | Instituto Nacional de Matemática Pura e Aplicada |

Zoom: | Contact Rose McCarty |

**Abstract:**

In this talk, we take a look under the hood of last week’s talk by Matt Baker: we inspect the foundation of a matroid.

The first desired properties follow readily from its definition: the foundation represents the rescaling classes of the matroid and shows a functorial behaviour with respect to minors and dualization.

Monday, September 14, 2020 — 11:30 AM EDT

**Title: **Extensions of the Erdős-Ko-Rado theorem to 2-intersecting perfect matchings and 2-intersecting permutations

Speakers: | Andriaherimanana Sarobidy Razafimahatratra & Mahsa Nasrollahi Shirazi |

Affiliation: | University of Regina |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

The Erdős-Ko-Rado (EKR) theorem is a classical result in extremal combinatorics. It states that if n and k are such that $n\geq 2k$, then any intersecting family F of k-subsets of [n] = {1,2,...,n} has size at most $\binom{n-1}{k-1}$. Moreover, if n>2k, then equality holds if and only if F is a canonical intersecting family; that is, $\bigcap_{A\in F}A = \{i\}$, for some i in [n].

Friday, September 11, 2020 — 3:30 PM EDT

**Title:** Further progress towards Hadwiger's conjecture

Speaker: | Luke Postle |

Affiliation: | University of Waterloo |

Zoom: | Please email Emma Watson. |

**Abstract:**

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.

Monday, September 7, 2020 — 11:30 AM EDT

**Title:** Projective Planes, Finite and Infinite

Speaker: | Eric Moorhouse |

Affiliation: | University of Wyoming |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

A projective plane is a point-line incidence structure in which every pair of distinct points has a unique joining line, and every pair of distinct lines meets in a unique point. Equivalently (as described by its incidence graph), it is a bipartite graph of diameter 3 and girth 6.

Friday, September 4, 2020 — 3:30 PM EDT

**Title:** Recent proximity results in integer linear programming

Speaker: | Joseph Paat |

Affiliation: | UBC Sauder School of Business |

Zoom: | Please email Emma Watson. |

**Abstract:**

We consider the proximity question in integer linear programming (ILP) --- Given a vector in a polyhedron, how close is the nearest integer vector? Proximity has been studied for decades with two influential results due to Cook et al. in 1986 and Eisenbrand and Weismantel in 2018. We derive new upper bounds on proximity using sparse integer solutions and mixed integer relaxations of the integer hull. When compared to previous bounds, these new bounds depend less on the dimensions of the constraint matrix and more on the data in the matrix.

Monday, August 31, 2020 — 11:30 AM EDT

**Title:** Scaffolds

Speaker: | William J. Martin |

Affiliation: | Worcester Polytechnic Institute |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

Building on the work of various authors who have used tensors in the study of association schemes and spin models, I propose the term "scaffold" for certain tensors that have been represented by what are sometimes called "star-triangle diagrams" in the literature. The main goal of the talk is to introduce and motivate these objects which somewhat resemble partition functions as they appear in combinatorics. (The exact definition is too cumbersome to include here.)

Friday, August 28, 2020 — 3:30 PM EDT

**Title:** Pure pairs

Speaker: | Sophie Spirkl |

Affiliation: | University of Waterloo |

Zoom: | Please email Emma Watson. |

**Abstract:**

A pure pair in a graph G is a pair of subsets A and B of the vertex set such that between A and B, either all edges or no edges are present in G. This concept was first introduced in connected with the Erdos-Hajnal conjecture, but has since developed a life of its own. I will give an overview of results and open questions on pure pairs.

Based on joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour.

Monday, August 24, 2020 — 11:30 AM EDT

**Title:** Laplacian Quantum Fractional Revival On Graphs

Speakers: |
Bobae Johnson, August Liu, Malena Schmidt, Neo Yin |

Affiliation: | York University |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

Given a set of quantum bits, we can model their interactions using graphs. The continuous-time quantum walks on a graph can be viewed as the Schrödinger dynamics of a particle hopping between adjacent vertices. In this talk, the transition matrix of the continuous-time quantum walk is given by $e^{-itL}$, where $L$ is the graph’s Laplacian matrix.

Friday, August 21, 2020 — 3:30 PM EDT

**Title:** An Algorithmic Reduction Theory for Binary Codes: LLL and more

Joint work with Thomas Debris-Alazard and Wessel van Woerden

Speaker: | Léo Ducas |

Affiliation: | Centrum Wiskunde & Informatica (CWI) |

Zoom: | Please email Emma Watson |

**Abstract:**

Lattice reduction is the task of finding a basis of short and somewhat orthogonal vectors of a given lattice. In 1985 Lenstra, Lenstra and Lovasz proposed a polynomial time algorithm for this task, with an application to factoring rational polynomials. Since then, the LLL algorithm has found countless application in algorithmic number theory and in cryptanalysis.

Monday, August 17, 2020 — 11:30 AM EDT

**Title:** State transfer and the size of the graph

Speaker: | Gabriel Coutinho |

Affiliation: | Universidade Federal de Minas Gerais |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

If there is perfect state transfer between two vertices at distance d, how small can the graph be compared to d? This question is motivated by the fact that the known infinite families of graphs admitting state transfer at increasingly large distances are all obtained from graph products, thus their sizes grow exponentially compared to their diameter.

Friday, August 14, 2020 — 3:30 PM EDT

**Title:** Constructing broken SIDH parameters: a tale of De Feo, Jao, and Plut's serendipity.

Speaker: | Chloe Martindale |

Affiliation: | University of Bristol |

Zoom: | This event has been cancelled. |

**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. Of importance in this talk will be 'endomorphisms' associated to elliptic curves: these are functions that map an elliptic curve to itself which also satisfy some nice properties.

Monday, August 10, 2020 — 11:30 AM EDT

**Title:** What do graph planarity and homomorphism counts have to do with quantum mechanics?

Speaker: | David Roberson |

Affiliation: | Technical University of Denmark |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

I will introduce the notion of quantum isomorphisms of graphs. These are defined in terms of a game in which two cooperating players attempt to convince a referee that two given graphs are isomorphic.

Thursday, August 6, 2020 — 2:30 PM EDT

**Title: **Subdivergence-free gluings of trees

Speaker: | Jordan Long |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

Motivated by questions in quantum field theory, we introduce a purely combinatorial problem of counting subdivergence-free gluings of trees. We present closed-form expressions counting subdivergence-free gluings for four different families of trees, as well as an algorithm to count subdivergence-free gluings of arbitrary pairs of trees. This is joint work with Clair Dai and Karen Yeats.

Thursday, August 6, 2020 — 2:30 PM EDT

**Title:** Counting the $c_2$ invariant on the circulant family of graphs

Speaker: | Mushegh Shahinyan |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

The algebro-geometric invariant on Feynman Diagrams called the $c_2$ invariant is a useful tool for detecting properties of Feynman periods. We present this identity on graphs that originate from the scalar $\phi_4$-theory with a purely combinatorial perspective and go over some strategies for computing it. We will further narrow our focus onto the circulant family of graphs and present some explicit results.

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Indigenous Initiatives Office.