Events

Approximately Counting Flows via Generating Function Optimization

Abstract: In this talk, we will present recent new lower bounds on the number of non-negative integer flows on a directed acyclic graph with specified total vertex flows (or equivalently, the number of lattice points of a given flow polytope, or the coefficients of the A-type Kostant partition function). We will also give a sketch of the proof, which involves three main parts: (1) prove a certain log-concavity property of the associated multivariate generating function, (2) prove bounds on the coefficients in terms of an associated optimization problem, and (3) dualize the optimization problem to obtain the desired lower bounds. If time permits, we will also briefly discuss other applications of this technique, including to approximating Kostka numbers and to the traveling salesperson problem. Joint work with Alejandro Morales, and with Petter Brändén and Igor Pak.

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

Title: LP based approximation algorithm for an stochastic matching problem

Abstract: Consider the random graph model where each edge e has a fixed weight w_e and it is independently present in the graph with probability p_e​. Given these probabilities, we want to construct a maximum weight matching in the graph. One can only determine if an edge is present by querying it, and if an edge is present, it must be irrevocably included in the matching. Additionally, each vertex i can be queried no more than t_i times. The goal is to device an adaptive policy (algorithm) to query the edges of the graph one by one in order to maximize the expected weight of the matching.

In this talk we present an elegant LP-based constant-factor approximation algorithm with respect to the optimal adaptive policy for the problem.

This is one of the results due to Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra, in their paper "When LP is the Cure for your Matching Woes" from 2011.

Graph Property Testing using the Container Method

Abstract: The Graph and Hypergraph Container Methods have recently been used to obtain multiple striking results across different areas of mathematics. In this talk, we will see how the graph container method is particularly well-suited for the study of some fundamental problems in graph property testing.

The main problem we will discuss in the talk is the Independent Set Testing problem introduced by Goldreich, Goldwasser, and Ron (1998). In this problem, we are given oracle access to a graph on $n$ vertices that either (i) contains an independent set on $\rho n$ vertices, or (ii) is $\epsilon$-far from the property in the sense that at least $\epsilon n^2$ edges must be removed from the graph to make it have an independent set of this size. We will introduce a new container lemma for the latter class of graphs and we will show how this lemma can be used to obtain a near-optimal solution to the Independent Set Testing problem. We will also discuss how variants and extensions of the new container lemma can be used to prove a variety of other results in property testing.

This is joint work with Cameron Seth.

Title: Combinatorial Nullstellensatz and the Erdős box problem

Abstract: In the talk, I will show how Lasoń’s generalization of Alon’s Combinatorial Nullstellensatz can be used to obtain lower bounds on Turán numbers of complete r-partite r-uniform hypergraphs. As an example, I will give a short and simple explicit construction of a hypergraph free of copies of the complete r-partite r-uniform  hypergraph with parts of size 2, thereby providing a lower bound for the so-called Erdős box problem. This asymptotically matches best known bounds when r ≤ 4. 

Title:Coefficient Positivity and Analytic Combinatorics

 Abstract: Given a rational function analytic at the origin, are its power series coefficients positive? We first motivate this question with historical background, examples and connections to decidability questions in combinatorics. We then present a method for proving positivity for a certain class of multivariate rational functions, by constructing explicit error bounds for an asymptotic expansion using analytic combinatorics in several variables. After applying our method to a couple of examples in the literature, including re-proving a (recently proved) conjecture of Gillis, Reznick and Zeilberger from 1983, we discuss the feasibility of completing certain steps in our analysis using methods from computer algebra.

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

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: Purifying arbitrarily noisy quantum states

Abstract: Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. For constant initial error parameter and dimension, our procedure has sample complexity asymptotically optimal in the final error parameter, and almost matches the known optimal protocol for qubits. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.  Joint work with Andrew Childs, Honghao Fu, Zhi Li, Maris Ozols, Vedang Vyas. 

Title: Constructing cospectral graphs - a ``Prehistory’'

Abstract: I will present some old constructions of cospectral graphs, due Brendan McKay and myself. I will also describe how we found some of these.

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.