Events

Abstract: A tournament is an orientation of a complete graph, and in terms of structural questions, tournaments are often a natural analogue of graphs. Neumann-Lara, in 1982, defined what it means to colour a tournament. Only recently, in 2023, Aboulker, Aubian, Charbit and Lopes defined what the clique number of a tournament is — but it is a bit more complicated than in graphs. What can we say about these parameters, from a structural and computational point of view? There are a few things to say, including a recent joint result with Logan Crew, Xinyue Fan, Hidde Koerts, and Ben Moore.

[Many of you know the severe consequences that a COVID infection has had for my family. I would consider it a kindness if attendees would wear masks. I will provide free masks for those who may need them.]

Abstract:We study algorithmic matroid intersection coloring. We give the first polynomial-time O(1)-approximation algorithm to color O(1) general matroids. Notably, for two general matroids we achieve a 2-approximation. Furthermore, we give a fully polynomial randomized approximation scheme (FPRAS) for coloring the intersection of two matroids when the maximum chromatic number is large. This yields the first polynomial-time algorithm for an asymptotic variant of Rota's Basis Conjecture.

AbstractPositroids were introduced by Postnikov in 2006 as a special class of matroids with nice combinatorial properties. Since 2008, starting with Suho Ho, several attempts have been made to describe the poset of quotients for this class of matroids in a combinatorial way. However, these descriptions are incomplete and always come from the same perspective. That is why we will explore new combinatorial objects and the context in which they arise (magic, polytopes, and antisymmetric algebras) to see if it is possible to describe this poset.

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

Abstract: Positroids are a subclass of matroids born in the study of the non-negative Grassmanian by Postnikov in 2006. Since then, there have been a plethora of combinatorial objects indexing positroids, two of these being the families of decorated and bicolored permutations, which are generalizations of classical permutations. These two families can be used to study properties of positroids, and as a byproduct we end up with useful ways to describe a group action on a deck of cards. In this context, we give a definition of invariants under this group action allowing us, as an application, to develop new magic tricks with unusual ways of shuffling cards.

Abstract:The satisfiability threshold of a random constraint satisfaction problem (CSP) is the density of constraints at which a random CSP instance transitions from being satisfiable to unsatisfiable with high probability. Much of the research on well known CSPs, including the $k$-SAT problem, $k$-XORSAT problem, hypergraph colouring, and systems of linear equations, has focused on determining satisfiability thresholds.

In this talk we consider systems of linear equations over finite commutative rings as CSPs, and build on the work of Ayre, Coja-Oghlan, Gao, and Müller, who determined the satisfiability threshold for random linear equations over a finite field. We determine when the satisfiability threshold is linear in the number of variables, and show that any linear threshold over a principal ideal ring coincides with the (unique) linear threshold over fields. We also determine the satisfiability threshold for some examples of non-principal ideal rings.

This is joint work with Jane Gao.

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

Abstract:  Given copies of a quantum state, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision. We say that such a protocol is triply efficient if it is sample efficient, time efficient, and uses measurements that entangle a constant number of copies of the state at a time.   A natural family of shadow tomography protocols based on random single-copy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient  shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all -qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample-efficient schemes are provably impossible using only single-copy measurements. This is joint work with Robbie King, Robin Kothari, and Ryan Babbush.