Events

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.

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