#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Thursday, March 31, 2022 1:00 PM EDT

**Title:** Multiplying quantum Schubert polynomials using combinatorics

Speaker: | Laura Colmenarejo |

Affiliation: | NC State University |

Zoom: | Contact Logan Crew or Olya Mandelshtam |

**Abstract:**

Schubert polynomials are a very interesting family of polynomials in algebraic geometry due to their relation with the cohomology of the flag variety. Moreover, they are also very interesting from a combinatorial point of view because they can be considered generalizations of Schur functions.

Tuesday, March 29, 2022 3:00 PM EDT

**Title:** Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Speaker: | Zishen Qu |

Affiliation: | University of Waterloo |

Zoom: | http://matroidunion.org/?page_id=2477 or contact Shayla Redlin |

**Abstract:**

Finding sufficient conditions for a class of graphs to be Hamiltonian is an old problem, with a wide variety of conditions such as Dirac's degree condition and Whitney's theorem on 4-connected planar triangulations. We discuss some past results on sufficient conditions for Hamiltonicity involving the exclusion of fixed induced subgraphs, and some properties of the graphs involved in such results.

Monday, March 28, 2022 11:30 AM EDT

**Title:** Oriented Cayley Graphs with all eigenvalues being integer multiples of $\sqrt{\Delta}$

Speaker: | Xiaohong Zhang |

Affiliation: | University of Waterloo |

Zoom: | Contact Sabrina Lato |

**Abstract:**

Let $G$ be a finite abelian group. An oriented Cayley graph on $G$ is a Cayley digraph $X(G,C)$ such that $C \cap (-C)=\emptyset$. Consider the $(0,1,-1)$ skew-symmetric adjacency matrix of an oriented Cayley graph $X=X(G,C)$.

Friday, March 25, 2022 3:30 PM EDT

**Title:** The chromatic number of triangle-free hypergraphs

Speaker: | Lina Li |

Affiliation: | University of Waterloo |

Location: | MC 5501 or please contact Emma Watson for Zoom link |

**Abstract:**

A classical result of Johansson showed that for any triangle-free graph $G$ with maximum degree $\Delta$, it chromatic number is $O(\Delta/\log\Delta)$. This result was later generalized to all rank 3 hypergraphs due to the work of Copper and Mubayi. In this talk, I will present a common generalization of the above results to all hypergraphs, and this is sharp apart from the constant.

Thursday, March 24, 2022 1:00 PM EDT

**Title:** Sorting probabilities for Young diagrams and beyond

Speaker: | Greta Panova |

Affiliation: | University of Southern California |

Zoom: | Contact Logan Crew or Olya Mandelshtam |

**Abstract:**

Sorting probability for a partially ordered set P is defined as the min |Pr[x<y] - Pr[y<x]| going over all pairs of elements x,y in P, where Pr[x<y] is the probability that in a uniformly random linear extension (extension to total order) x appears before y.

The celebrated 1/3-2/3 conjecture states that for every poset the sorting probability is at most 1/3, i.e. there are two elements x and y, such that 1/3\leq Pr[x<y] \leq 2/3.

Tuesday, March 22, 2022 5:00 PM EDT

**Title:** Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

Speaker: | O-joung Kwon |

Affiliation: | Hanyang University |

Zoom: | http://matroidunion.org/?page_id=2477 or contact Shayla Redlin |

**Abstract:**

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red.

Monday, March 21, 2022 11:30 AM EDT

**Title:** Decomposing graphs and hypergraphs into complete bipartite subgraphs

Speaker: | Sebastian Cioaba |

Affiliation: | University of Delaware |

Zoom: | Contact Sabrina Lato |

**Abstract:**

The problem of decomposing (partitioning or covering) graphs into complete bipartite subgraphs (bicliques) has a long history. In this talk, I will describe the basic results including the use of spectral methods, the extension of the problem to hypergraphs and present some of the open problems in this area.

Friday, March 18, 2022 3:30 PM EDT

**Title:** Fixed-size schemes for certification of large quantum systems

Speaker: | Laura Mancinska |

Affiliation: | QMATH, University of Copenhagen |

Location: | MC 5501 or please contact Emma Watson for Zoom link |

**Abstract:**

In this talk I will introduce the concept of self-testing which aims to answer the fundamental question of how do we certify proper functioning of black-box quantum devices. We will see that there is a close link between self-testing and representations of algebraic relations. We will leverage this link to propose a family of protocols capable of certifying quantum states and measurements of arbitrarily large dimension with just four binary-outcome measurements.

This is a joint work with Chris Schafhauser and Jitendra Prakash.

Thursday, March 17, 2022 1:00 PM EDT

**Title: **A Multijection of Cokernels

Speaker: | Alex McDonough |

Affiliation: | UC Davis |

Zoom: | Contact olya.mandelshtam@uwaterloo.ca |

**Absract:**

I discovered an intriguing linear algebra relationship which I call a multijection. I used this construction to solve an open problem about higher-dimensional sandpile groups, but I think that it has more to say.

Tuesday, March 15, 2022 3:00 PM EDT

**Title:** On packing dijoins in digraphs and weighted digraphs

Speaker: | Ahmad Abdi |

Affiliation: | LSE |

Zoom: | http://matroidunion.org/?page_id=2477 or email shayla.redlin@uwaterloo.ca |

**Abstract:**

Let D=(V,A) be a digraph. A dicut is the set of arcs in a cut where all the arcs cross in the same direction, and a dijoin is a set of arcs whose contraction makes D strongly connected. It is known that every dicut and dijoin intersect. Suppose every dicut has size at least k.

Friday, March 11, 2022 3:30 PM EST

**Title:** Strongly nonexpansive mappings revisited: uniform monotonicity and operator splitting

Speaker: | Walaa Moursi |

Affiliation: | University of Waterloo |

Location: | MC 5501 or please contact Emma Watson for Zoom link |

**Abstract:**

The correspondence between the class of nonexpansive mappings and the class of maximally monotone operators via the reflected resolvents of the latter has played an instrumental role in the convergence analysis of the splitting methods. Indeed, the performance of some of these methods, e.g., Douglas–Rachford and Peaceman–Rachford methods hinges on iterating the so-called splitting operator associated with the individual operators.

Thursday, March 10, 2022 1:00 PM EST

**Title:** Type B q-Stirling numbers

Speaker: | Joshua Swanson |

Affiliation: | USC |

Location: | MC 6029 or contact Logan Crew for Zoom link |

**Abstract:**

The Stirling numbers of the first and second kind are classical objects in enumerative combinatorics which count the number of permutations or set partitions with a given number of blocks or cycles, respectively. Carlitz and Gould introduced q-analogues of the Stirling numbers of the first and second kinds, which have been further studied by many authors including Gessel, Garsia, Remmel, Wilson, and others, particularly in relation to certain statistics on ordered set partitions.

Thursday, March 10, 2022 11:30 AM EST

**Title:** “Lattice-Based Zero-Knowledge Arguments for Integer Relations” by Benoit Libert, San Ling, Khoa Nguyen, and Huaxiong Wang

Speaker: | Camryn Steckel |

Affiliation: | University of Waterloo |

Zoom: | Contact Jesse Elliott |

**Abstract:**

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial size modulus q.

Tuesday, March 8, 2022 4:00 PM EST

**Title:** Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

Speaker: | Sang-il Oum |

Affiliation: | Institute for Basic Science / KAIST |

Zoom: | Join via http://matroidunion.org/?page_id=2477 or please email Shayla Redlin |

**Abstract:**

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field $\mathbb F$, the list contains only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)].

Monday, March 7, 2022 11:30 PM EST

**Title:** Polynomial ideals, association schemes, and the Q-polynomial property

Speaker: | Bill Martin |

Afiliation: | Worcester Polytechnic Institute |

Zoom: | Contact Sabrina Lato |

**Abstract:**

Let X ⊆ S^{m−1} be a spherical code in C^m. We study the ideal I ⊆ C[z_1, . . . , z_m] of polynomials that vanish on the points of X: I = { F(z) | (∀a ∈ X) (F(a) = 0) }. The primary example of interest is where the Gram matrix of X is proportional to the first idempotent in some Q-polynomial ordering of an association scheme (X, R) defined on X.

Friday, March 4, 2022 3:30 PM EST

**Title:** Counting planar maps, 50 years after William Tutte

Speaker: | Mireille Bousquet-Mélou |

Affiliation: | CNRS, Université de Bordeaux |

Location: | MC 5501 or please contact Emma Watson for Zoom link |

**Abstract:**

Every planar map can be properly coloured with four colours. But how many proper colourings has, on average, a planar map with $n$ edges? What if we allow a prescribed number of "monochromatic" edges, the endpoints of which share the same colour? What if we have $q$ colours rather than four?

Thursday, March 3, 2022 1:00 PM EST

**Title:** Lineup polytopes and exclusion principles

Speaker: | Federico Castillo |

Affiliation: | Universidad Catolica de Chile |

Zoom link: | Contact Logan Crew |

**Abstract:**

The set of all possible spectra of 1-reduced density operators for systems of N particles on a d-dimensional Hilbert space is a polytope called hypersimplex and this is related to Pauli's exclusion principle. If the spectrum of the original density operators is fixed, the set of spectra (ordered decreasingly) of 1-reduced density operators is also a polytope.

Tuesday, March 1, 2022 11:00 AM EST

**Title:** Packing and covering balls in planar graphs

Speaker: | Louis Esperet |

Affiliation: | G-SCOP Laboratory |

Zoom: | Join via http://matroidunion.org/?page_id=2477 or please email Shayla Redlin |

**Abstract:**

The set of all vertices at distance at most r from a vertex v in a graph G is called an r-ball. We prove that the minimum number of vertices hitting all r-balls in a planar graph G is at most a constant (independent of r) times the maximum number of vertex-disjoint r-balls in G.

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 co-ordinated within our Office of Indigenous Relations.