Seminar

Title:Vanishing of Schubert coefficients

 Abstract: Schubert coefficients are nonnegative integers that arise in Algebraic Geometry and play a central role in Algebraic Combinatorics. It is a major open problem whether they have a combinatorial interpretation, i.e, they are in #P. In this talk we discuss the closely related problem of the vanishing of Schubert coefficients. We prove that this vanishing problem is rather low in the polynomial hierarchy and discuss implications of this result.

This is joint work with Igor Pak.

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

Title: Intersection of Matroids

Abstract: We study simplicial complexes (hypergraphs closed under taking subsets) that are the intersection of a given number k of matroids. We prove bounds on their chromatic numbers (the minimum number of edges required to cover the ground set) and their list chromatic numbers. Settling a conjecture of Kiraly and Berczi--Schwarcz--Yamaguchi, we prove that the list chromatic number is at most k times the chromatic number. The tools used are in part topological. If time permits, I will also discuss a result proving that the list chromatic number of the intersection of two matroids is at most the sum of the chromatic numbers of each matroid, improving a result by Aharoni and Berger from 2006. The talk is based on works joint with Ron Aharoni, Eli Berger, and Daniel Kotlar. In this talk, there is no assumption about background knowledge of matroid theory or algebraic topology.

Title:Smooth points on positroid varieties and planar N=4 supersymmetric Yang-Mills theory

 Abstract: Positroid varieties are subvarieties in the Grassmannian defined by cyclic rank conditions and which are related to Schubert varieties. We will provide a criterion for whether positroid varieties are smooth at certain distinguished points, and we will show that this information is sufficient to determine smoothness for the entire positroid variety. This will involve looking at combinatorial diagrams called "affine pipe dreams." We can also form a partial order on positroid varieties given by deletion and contraction, such that there is closure for smooth positroid varieties, and we will characterize the minimal singular elements in this order. Finally, we will discuss a couple of connections between the techniques of this work and planar N=4

SYM: the BCFW bridge decomposition and inverse soft factors.

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

Title: Quantum graphs, subfactors and tensor categories

Abstract: Graphs and their noncommutative analogues are interesting objects of study from the perspectives of operator algebras, quantum information and category theory. In this talk we will introduce  equivariant graphs with respect to a quantum symmetry along with examples such as classical graphs, Cayley graphs of finite groupoids, and their quantum analogues. We will also see these graphs can be constructed concretely by modeling a quantum vertex set by an inclusion of operator algebras and the quantum edge set by an equivariant endomorphism that is an idempotent with respect to convolution/Schur product. Equipped with this viewpoint and tools from subfactor theory, we will see how to obtain all these idempotents using higher relative commutants and the quantum Fourier transform. Finally, we will state a quantum version of Frucht's Theorem, showing that every quasitriangular finite quantum groupoid arises as certain automorphisms of some categorified graph.

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: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: 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: 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.

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.