Georgia Institute of Technology College of Sciences

We will outline the proof that gives a positive solution to Weaver's conjecture $KS_2$. That is, we will show that any isotropic collection of vectors whose outer products sum to twice the identity can be partitioned into two parts such that each part is a small distance from the identity. The distance will depend on the maximum length of the vectors in the collection but not the dimension (the two requirements necessary for Weaver's reduction to a solution of Kadison--Singer). This will include introducing a new technique for establishing the existence of certain combinatorial objects that we call the "Method of Interlacing Polynomials." This talk is intended to be accessible by a general mathematics audience, and represents joint work with Dan Spielman and Nikhil Srivastava.

The traveling salesman problem (TSP) is the most famous problem in discrete optimization. Given $n$ cities and the costs $c_{ij}$ for traveling from city $i$ to city $j$ for all $i,j$, the goal of the problem is to find the least expensive tour that visits each city exactly once and returns to its starting point. We consider cases in which the costs are symmetric and obey the triangle inequality. In 1954, Dantzig, Fulkerson, and Johnson introduced a linear programming relaxation of the TSP now known as the subtour LP, and used it to find the optimal solution to a 48-city instance. Ever since then, the subtour LP has been used extensively to find optimal solutions to TSP instances, and it is known to give extremely good lower bounds on the length of an optimal tour. Nevertheless, the quality of the subtour LP bound is poorly understood from a theoretical point of view. For 30 years it has been known that it is at least 2/3 times the length of an optimal tour for all instances of the problem, and it is known that there are instances such that it is at most 3/4 times the length of an optimal tour, but no progress has been made in 30 years in tightening these bounds. In this talk we will review some of the results that are known about the subtour LP, and give some new results that refine our understanding in some cases. In particular, we resolve a conjecture of Boyd and Carr about the ratio of an optimal 2-matching to the subtour LP bound in the worst case. We also begin a study of the subtour LP bound for the extremely simple case in which all costs $c_{ij}$ are either 1 or 2. For these instances we can show that the subtour LP is always strictly better than 3/4 times the length of an optimal tour. These results are joint work with Jiawei Qian, Frans Schalekamp, and Anke van Zuylen.

Forbidding (undirected or directed) paths in graphs, what can be easier? Yet we show that in the context of coloring problems (CSP) and structural graph theory, this is related to the notions tree depth, (restricted) dualities, bounded expansion and nowhere dense classes with applications both in and out of combinatorics.

I will talk about new approximation algorithms for the Asymmetric Traveling Salesman Problem (ATSP) when the costs satisfy the triangle inequality. Our approach is based on constructing a "thin" spanning tree from the solution of a classical linear programming relaxation of the problem and augmenting the tree to an Eulerian subgraph. I will talk about Goddyn's conjecture on the existence of such trees and its relations to nowhere-zero flows. I will present an O(log n/log log n) approximation algorithm that uses a new randomized rounding method. Our rounding method is based on sampling from a distribution and could be of independent interest. Also, I will talk about the special case where the underlying undirected graph of the LP relaxation of the problem has bounded genus. This is the case for example, when the distance functions are shortest paths in a city with few bridges and underpasses. We give a constant factor approximation algorithm in that case. The first result is a joint work with A. Asadpour, M. Goemans, A. Madry and S. Oveis Gharan, and the second result is a joint work with S. Oveis Gharan.