Events

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: Odd-Ramsey numbers of complete bipartite graphs

Abstract: In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs ℋ, defined as the minimum number of colours needed to colour the edges of the complete graph so that every copy of a graph H in ℋ intersects some colour class by an odd number of edges. In recent joint work with Simona Boyadzhiyska, Shagnik Das, and Kaline Petrova, we focus on the odd-Ramsey numbers of complete bipartite graphs. First, using polynomial methods, we completely resolve the problem when ℋ is the family of all spanning complete bipartite graphs on n vertices. We then focus on its subfamilies. In this case, we establish an equivalence between the odd-Ramsey problem and a well-known problem from coding theory, asking for the maximum dimension of a linear binary code avoiding codewords of given weights. We then use known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs.