Atlanta Combinatorics
Colloquium

The Atlanta Combinatorics Colloquium is a seminar in discrete mathematics jointly hosted by the combinatorics groups at the Georgia Institute of Technology, Georgia State University, and Emory University.

Upcoming talks

Save the date for the following upcoming talks!

October 21, 2022: Bhargav Narayanan, Rutgers University.

This talk will be hosted by Georgia Tech.

Time: 4pm
Location: Instructional Center 105

Title: Friendly Bisections of Random Graphs

Abstract: It is easy to partition the vertices of any graph into two sets where each vertex has at least as many neighbours across as on its own side; take any maximal cut! Can we do the opposite? This is not possible in general, but Füredi conjectured in 1988 that it should nevertheless be possible on a random graph. I shall talk about our recent proof of Füredi's conjecture: with high probability, the random graph $$G(n,1/2)$$ on an even number of vertices admits a partition of its vertex set into two parts of equal size in which $$n - o(n)$$ vertices have more neighbours on their own side than across.

November 11, 2022: Penny Haxell, University of Waterloo.

This talk will be hosted by Georgia State.

Time: 4pm
Location: 25 Park Place, Room 223

Title: The Integrality Gap for the Santa Claus Problem

Abstract: In the max-min allocation problem, a set of players are to be allocated disjoint subsets of a set of indivisible resources, such that the minimum utility among all players is maximized. In the restricted variant, also known as the Santa Claus Problem, each resource ("toy") has an intrinsic positive value, and each player ("child") covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.

Bezakova and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the Configuration LP of Bansal and Sviridenko, and bounds on its integrality gap. The existing algorithms and integrality gap estimations tend to be based one way or another on a combinatorial local search argument for finding perfect matchings in certain hypergraphs.

Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, from the previously best known bound of 3.808 for the general problem to 3.534. We also address the well-studied special case in which resources can take only two values, and improve the integrality gap in most cases. This is based on joint work with Tibor Szabo.

December 7, 2022: David Conlon, California Institute of Technology.

This talk will be hosted by Emory.

Time: 3pm
Location: W301, Mathematics and Science Center, Emory University

Title: Sumset Estimates in Higher Dimensions

Abstract: We will describe recent progress, in joint work with Jeck Lim, on the study of sumset estimates in higher dimensions. The basic question we discuss is the following: given a subset $$A$$ of $$d$$-dimensional space and a linear transformation $$L$$, how large is the sumset $$A + LA$$?

Click on an event to see the details.