Lecture

Title: Forbidding some induced cycles in a graph

Abstract:  We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain lengths in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols, Kapoor, and Vušković provided a structural description of the class of even-hole-free graphs.

Title: Hadamard’s Maximal Determinant Problem and Generalisations

Abstract:  Any matrix $M$ of order $n$ with entries taken from the complex unit disk satisfies Hadamard’s determinantal inequality $|\det M|\leq n^{n/2}$. Matrices meeting this bound with equality have pairwise orthogonal rows and columns. Such matrices are known as Hadamard matrices, and character tables of finite abelian groups give examples at every order.

Title: The ADMM:  Past, Present, and Future

Abstract: Over the past 15 years, the alternating direction method of multipliers (ADMM) has become a standard optimization method.  This talk will cover the origins of the ADMM, its subsequent development, and what to expect in the future.

Title: An introduction to discrete quantum walks

Abstract: A discrete quantum walk is determined by a unitary matrix representation of a graph. In this talk, I will give an overview of different quantum walks, and show how the spectral information of the unitary matrix representation links properties of the walks to properties of the graphs. Part of this talk will be based on the book, Discrete Quantum Walks on Graphs and Digraphs, by Chris and me.

Title: Integer programs with bounded subdeterminants and two nonzeros per row

Abstract: Determining the complexity of integer linear programs with integer coefficient matrices whose subdeterminants are bounded by a constant is currently a very actively discussed question in the field. In this talk, I will present a strongly polynomial-time algorithm for such integer programs with the further requirement that every constraint contains at most two variables. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k = 0 (bipartite graphs) and for k = 1.

This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky, which recently appeared at FOCS this year.

Title: Approximate Counting via Lorentzian Polynomials and Entropy Optimization

Abstract: Over the past 20 years, Lorentzian and real stable polynomials have been used to derive a number of combinatorial theorems, from log-concavity statements to counting and volume bounds. One significant thread of this research lies in the utilization of entropy optimization methods to approximately count certain combinatorial objects, such as the matchings of a bipartite graph, the intersection of the sets of bases of two matroids, and the integer points of various polytopes in general. In this talk, we will discuss various results one can achieve using such methods.

Title: Jack Derangements

Abstract: For each integer partition $\lambda \vdash n$ we give a simple combinatorial formula for the sum of the Jack character $\theta^\lambda_\alpha$ over the integer partitions of $n$ with no singleton parts. For $\alpha = 1,2$ this gives closed forms for the eigenvalues of the permutation and perfect matching derangement graphs, resolving an open question in algebraic graph theory. Our proofs center around a Jack analogue of a hook product related to Cayley's $\Omega$--process in classical invariant theory, which we call \emph{the principal lower hook product}.

Title: Lineup polytopes and applications in quantum physics

Abstract:  To put it simply, Pauli's exclusion principle is the reason why we can't walk through walls without getting hurt. Pauli won the Nobel Prize in Physics in 1945 for the formulation of this principle. A few years later, this principle received a geometrical formulation that is still overlooked today. This formulation uses the eigenvalues of certain matrices (which represent a system of elementary particles, for example electrons). These eigenvalues form a symmetric geometric object obtained by cutting a hypercube: it is a hypersimplex.

Title: On the Adaptivity Gap of Stochastic Orienteering

Abstract: This talk highlights the stochastic orienteering problem, in which we are given a budget B and a graph G=(V,E) with edge distances d(u,v) and a starting vertex x. Each vertex v represents a job with a deterministic reward and a random processing time, drawn from a known distribution.

Title: Bipartite Matching in Almost-Linear Time and More

Abstract:  This talk will present an algorithm that computes maximum bipartite matchings in m^{1 + o(1)} time, and discuss its connections with optimization, graph algorithms, and data structures.