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


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: or contact Shayla Redlin


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


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


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


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: or contact Shayla Redlin


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


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


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


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: or email


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


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


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


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 or please email Shayla Redlin


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


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


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


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 or please email Shayla Redlin


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.

  1. 2023 (113)
    1. October (4)
    2. September (10)
    3. August (7)
    4. July (19)
    5. June (21)
    6. May (12)
    7. April (5)
    8. March (17)
    9. February (10)
    10. January (8)
  2. 2022 (150)
    1. December (8)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  3. 2021 (103)
  4. 2020 (119)
  5. 2019 (167)
  6. 2018 (136)
  7. 2017 (103)
  8. 2016 (137)
  9. 2015 (136)
  10. 2014 (88)
  11. 2013 (48)
  12. 2012 (39)
  13. 2011 (36)
  14. 2010 (40)
  15. 2009 (40)
  16. 2008 (39)
  17. 2007 (15)