Events

Title: Constructing cospectral graphs - a ``Prehistory’'

Abstract: I will present some old constructions of cospectral graphs, due Brendan McKay and myself. I will also describe how we found some of these.

Title: Unavoidable flats in matroids representable over a finite field

Abstract: For a positive integer k and finite field F, we prove that every simple F-representable matroid with sufficiently high rank has a rank-k flat which either is independent, or is a projective or affine geometry over a subfield of F.  As a corollary, we obtain the following Ramsey theorem: given an F-representable matroid of sufficiently high rank and any 2-colouring of its points,  there is a monochromatic rank-k flat.  This is joint work with Jim Geelen and Peter Nelson. 

Title: Cyclotomic generating functions

Abstract: It is a remarkable fact that for many statistics on finite sets of combinatorial objects, the roots of the corresponding generating function are each either a complex root of unity or zero. These and related polynomials have been studied for many years by a variety of authors from the fields of combinatorics, representation theory, probability, number theory, and commutative algebra. We call such polynomials *cyclotomic generating functions* (CGFs). We will review some of the many known examples and give results to classify the asymptotic behavior of their coefficient sequences in certain regimes.

Joint work with Sara Billey.

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

Abstract: In this talk, we will cover the paper of Svensson and Tarnawski that shows that perfect matching in general (non-bipartite) graphs in is quasi-NC. Similar to the work of Fenner, Gurjar and Thierauf (covered earlier in the reading group), the approach is to derandomize the isolation lemma for the perfect matching polytope by applying weight functions to iteratively restrict to subfaces of the polytope. However, the perfect matching polytope in general graphs is not as well-structured as it is in bipartite graphs. The faces of the polytope no longer correspond to subgraphs and now involve additional tight odd set constraints that need to be dealt with. This makes it so that a cycle with non-zero circulation may still exist in the support of the new face. Additionally, the existence of odd cycles in the graph breaks the cycle counting argument used in the paper of Fenner, Gurjar, Thierauf. We will see how Svensson and Tarnawski deal with these issues in the talk.

Title: Rotation-invariant web bases from hourglass plabic graphs and symmetrized six-vertex configurations

Abstract: Many combinatorial objects with strikingly good enumerative formulae also have remarkable dynamical behavior and underlying algebraic structure. In this talk, we consider the promotion action on certain rectangular tableaux and explain its small, predictable order by reinterpreting promotion as a rotation in disguise. We show how the search for this visual explanation of combinatorial dynamics led to the solution of an algebraic problem involving web bases and a generalization of the six-vertex model of statistical physics. We find that this framework includes several unexpected combinatorial objects of interest: alternating sign matrices, plane partitions, and their symmetry classes (joint with Ashleigh Adams). This talk is based primarily on joint work with Christian Gaetz, Stephan Pfannerer, Oliver Pechenik, and Joshua P. Swanson.

Title: Hypercube decompositions and combinatorial invariance for Kazhdan-Lusztig polynomials

Abstract: Kazhdan-Lusztig polynomials are of foundational importance in geometric representation theory. Yet the Combinatorial Invariance Conjecture, due to Lusztig and to Dyer, suggests that they only depend on the combinatorics of Bruhat order. I'll describe joint work with Grant Barkley in which we adapt the hypercube decompositions introduced by Blundell-Buesing-Davies-Veličković-Williamson to prove this conjecture for Kazhdan-Lusztig R-polynomials in the case of elementary intervals in the symmetric group. This significantly generalizes the main previously known case of the conjecture, that of lower intervals.

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

Title: Determinantal ideals of graphs

Abstract: Let $A$ ($D$) denote the adjacency (distance) matrix of a graph $G$ with $n$ vertices. We define the $k$-th determinantal ideal of $M_X:=diag(x_1,x_2,\ldots ,x_n)+M$ as the ideal generated by all of its minors of size $k\leq n$. If $M=A$, we call this the $k$-th critical ideals of $G$. On the other hand, if $M=D$, we call it the $k$-th distance ideals of $G$. These algebraic objects are related to the spectrum of their corresponding graph matrices, their Smith normal form, and in consequence to their sandpile group for instance. In this talk, we will explore some of the properties and applications of these ideals. 

Title:Sufficient conditions for equality of skew Schur functions

 Abstract: : A pair of skew shapes are said to be skew equivalent if they admit the same number of semistandard Young tableaux of each weight, or in other words if the skew Schur functions they define are equal. A conjecture of McNamara and van Willigenburg gives necessary and sufficient combinatorial conditions for shapes to be skew equivalent, but neither direction was known to hold in general. We prove sufficiency. The techniques used are Hopf-algebraic in spirit and extend ideas used by Yeats to prove a simple case.

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

Title:Nearly optimal communication and query complexity of bipartite matching 

Abstract:I will talk about a recent paper (Blikstad, van den Brand, Efron, Mukhopadhyay, Nanongkai, FOCS 22) which gives near-optimal algorithms for bipartite matching (and several generalizations) in communication complexity, and several types of query complexity. We will focus only on the simplest case (i.e. unweighted bipartite matching),and will not assume any background on communication or query complexity.

Title: Concrete analysis of a few aspects of lattice-based cryptography

Abstract: A seminal 2013 paper by Lyubashevsky, Peikert, and Regev proposed using ideal lattices as a foundation for post-quantum cryptography, supported by a polynomial-time security reduction from the approximate Shortest Independent Vectors Problem (SIVP) to the Decision Learning With Errors (DLWE) problem in ideal lattices. In our concrete analysis of this multi-step reduction, we find that the reduction’s tightness gap is so significant that it undermines any meaningful security guarantees. Additionally, we have concerns about the feasibility of the quantum aspect of the reduction in the near future. Moreover, when making the reduction concrete, the approximation factor for the SIVP problem turns out to be much larger than anticipated, suggesting that the approximate SIVP problem may not be hard for the proposed cryptosystem parameters.