Future students

Abstract: In this talk, I will go through the paper of "Nash Social Welfare, Matrix Permanent, and Stable Polynomials" by Anari, Oveis Gharan, Saberi, Singh. We will consider the problem of allocating m items to n agents. Each agent has a value v_{ij} for item j. The goal is to construct an allocation A_1,...,A_n so as to maximize the Nash social welfare \prod_i \sum_{j in A_i} v_{ij}. We will prove a simple 1/e approximation for the problem.

The techniques involve proving a generalization of the Van Der Waerden theorem for bounding the permanent of a doubly-stochastic matrix. We setup a convex program relaxation of the problem. Using the aforementioned theorem, we show that a simple rounding procedure on the optimal solution of this program gives the 1/e-approximation.

Abstract: I will give an introductory talk about one of my favourite classes of matroids: gammoids. These arise as connectivity to a base set of vertices in a digraph.

Abstract: Billera, Jia, and Reiner (2009) introduced the quasisymmetric functions of matroids and showed that this defines a Hopf algebra homomorphism which is a valuative invariant, i.e., isomorphic matroids have the same quasisymmetric function and polytopal decompositions of matroid base polytopes define relations among the corresponding quasisymmetric functions. In this project we study an analogue in non-commuting variables, the word-quasisymmetric functions. To every matroid M we associate a word-quasisymmetric function ψ(M) and call this the chromatic word-quasisymmetric functions of a matroid. Matroids and word-quasisymmetric functions form Hopf algebras, and our map ψ between them is a homomorphism. We want to study the kernel, equivalently the image, of the map ψ from matroids to word-quasisymmetric functions, that is, we would like to understand which matroids are indistinguishable by the chromatic word-quasisymmetric functions. The map ψ is not an invariant, but we can show that it is valuative. Using Schubert matroids and nested matroids, special classes of matroids, we prove a lower bound of 2^d − d for the rank of the map ψ from matroids to the chromatic word-quasisymmetric functions in degree d and conjectured the upper bound of d! is tight. Recent AI supported work shows that our conjecture is true.

This is joint work with Raul Penaguiao.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.

Abstract: Quantum key distribution (QKD) protocols rely on the laws of physics for provably secure secret sharing, but the laws of physics are notoriously tricky to harness. If the laser being used for encoding is fluctuating in time, how does this affect the security guarantees? In this talk, I will cover the kinds of problems that can arise in physical realizations of QKD protocols and the problems that these might cause. After this, I will give a (far from exhaustive) overview of techniques that come up in dealing with such imperfections in the implementation. This will be open-ended, in the sense that questions that arise/different interests during the talk can dictate what we cover.

Abstract: Vertex decomposable simplicial complexes and geometrically vertex decomposable ideals have a lot of nice structure: they are shellable and Cohen–Macaulay, and the ideal version is also radical and glicci. There are many ways to attach an ideal to a graph, such as edge ideals, toric ideals, binomial edge ideals and star configurations, and the goal is to exploit the graph structure to decide whether the ideal is (geometrically) vertex decomposable. I will introduce these notions from scratch, with no commutative algebra assumed, and survey recent joint work, including a computer search of all graphs on 11 vertices and a conjecture for binomial edge ideals.  

Abstract: A 0-1 matrix M is perfect if the polyhedron {x ≥ 0 : Mx ≤ 1} is integral. Perfect matrices are closely related to perfect graphs and have several remarkable properties. In particular, perfectness is equivalent to total dual integrality, and perfect matrices admit an excluded-minor characterization.

A 0-1 matrix M is ideal if the polyhedron {x ≥ 0 : Mx ≥ 1} is integral. Unlike perfect matrices, ideal matrices do not correspond to a single well-understood class of combinatorial objects. In this talk, we will explore which of the remarkable properties of perfect matrices have counterparts for ideal matrices. We will discuss what is known, what fails, and some of the intriguing open questions that arise from this comparison.

Abstract: A $k$-sunflower is a family of $k$ distinct sets whose pairwise intersections all coincide. The Erd\H{o}s--Szemer\'edi conjecture asserts that for every $k \ge 3$ there is a constant $c_k < 2$ such that any $k$-sunflower-free family $\mathcal{F} \subseteq 2^{[n]}$ satisfies $|\mathcal{F}| \le c_k^{\,n}$. Bucic, He, and Lee recently proved this with an explicit bound.

In this talk we survey the problem and its place among sunflower questions, then work through the proof, centered on a vector-sunflower argument. We also discuss how the result relates to a related problem, the uniform Erd\H{o}s--Rado conjecture, which it does not settle. No prior background is assumed. 

Abstract: Determining whether a graph is k-colourable is a famously hard computational problem. Even when placing significant restrictions on the graph, the resulting problem is often NP-hard. In this talk, we focus on the case of restricting the diameter. Under the Exponential Time Hypothesis, there does not exist a sub-exponential algorithm for 3-colouring diameter-4 graphs or for 4-colouring diameter-2 graphs. Hence, the interesting remaining cases are 3-colouring graphs of diameter 2 or 3. We show that 3-colouring diameter-3 graphs can be solved in 2^O(n^{2/3−ε}) for any ε < 1/33 by providing an algorithm based on a structural result. This improves on the previous best known algorithm due to Dębski, Piecyk and Rzążewski.

This talk is based on joint work with Carla Groenland and Sophie Spirkl.

Abstract: Having seen the BB84 quantum key distribution protocol last week, this week we’ll see what it means for QKD to be secure, following the basic principle that “information gain implies disturbance”. We’ll talk about what authentication is needed for QKD’s security guarantees to hold, and other factors like device security and finite key effects.

Abstract: We study the H-chromatic symmetric functions X_G^H introduced by Eagles et al. (2022), which generalizes the chromatic symmetric function X_G to the context of H-colorings, which tracks graph homomorphisms G → H. We first show that self-chromatic symmetric functions X_G^G determine quantities like the connected components of a forest and the degree sequence of a caterpillar. We then show that the X_G^H's form a basis of the symmetric function ring for certain collections of (G,H), such as the self-CSFs of complete multipartite graphs. Lastly, we define and discuss H-chromatic polynomials as specializations of H-CSFs. This is joint work with Laura Pierson.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.