Snow And Theory

Cropped from src1 & src2 in gardens for karma

Prasad Tetali and Robin Thomas are mathematicians at Georgia Tech who are organizing the Conference Celebrating the 25th Anniversary of the ACO Program. ACO stands for our multidisciplinary program in Algorithms, Combinatorics and Optimization. The conference is planned to be held starting this Monday, January 9–11, 2017.

Today I say “planned” because there is some chance that Mother Nature could mess up our plans.

Atlanta is expected to get a “major” snow storm this weekend. Tech was already closed this Friday. It could be that we will still be closed Monday. The storm is expected to drop 1-6 inches of snow and ice. That is not so much for cities like Buffalo in the north, but for us in Atlanta that is really a major issue. Ken once flew here to attend an AMS-sponsored workshop and play chess but the tournament was canceled by the snowfall described here. So we hope that the planned celebration really happens on time.

Attendance is free, so check here for how to register.

A Few Of The Talks

The program has a wide array of speakers. There are 25 talks in all including two by László Babai. I apologize for not listing every one. I’ve chosen to highlight the following for a variety of “random” reasons.

László Babai
Graph Isomorphism: The Emergence of the Johnson Graphs

Abstract: One of the fundamental computational problems in the complexity class NP on Karp’s 1973 list, the Graph Isomorphism problem asks to decide whether or not two given graphs are isomorphic. While program packages exist that solve this problem remarkably efficiently in practice (McKay, Piperno, and others), for complexity theorists the problem has been notorious for its unresolved asymptotic worst-case complexity.

In this talk we outline a key combinatorial ingredient of the speaker’s recent algorithm for the problem. A divide-and-conquer approach requires efficient canonical partitioning of graphs and higher-order relational structures. We shall indicate why Johnson graphs are the sole obstructions to this approach. This talk will be purely combinatorial, no familiarity with group theory will be required.

This talk is the keynote of the conference. Hopefully Babai will update us all on the state of this graph isomorphism result. We have discussed here his partial retraction. I am quite interested in seeing what he has to say about the role of Johnson graphs. These were discovered by Selmer Johnson. They are highly special: they are regular, vertex-transitive, distance-transitive, and Hamilton-connected. I find it very interesting that such special graphs seem to be the obstacle to progress on the isomorphism problem.

Petr Hliněný
A Short Proof of Euler-Poincaré Formula

Abstract: We provide a short self-contained inductive proof of famous Euler-Poincaré Formula for the numbers of faces of a convex polytope in every dimension. Our proof is elementary and it does not use shellability of polytopes.

The paper for this talk is remarkably short, only 3 pages. Of course the result has been around since the 1700s and 1800s, and David Eppstein already has a list of 20 proofs of it, so what is the point? It has to do with ways of proving things and the kind of dialogue we can have with ourselves and/or others about what is needed and what won’t work. Imre Lakatos famously codified this process, with this theorem as a running example conjuring up the so-called Lakatosian Monsters. Perhaps the talk will slay the monsters, but it will have to brave some snow and ice first.

Luke Postle
On the List Coloring Version of Reed’s Conjecture

Abstract: In 1998, Reed conjectured that chromatic number of a graph is at most halfway between its trivial lower bound, the clique number, and its trivial upper bound, the maximum degree plus one. Reed also proved that the chromatic number is at most some convex combination of the two bounds. In 2012, King and Reed gave a short proof of this fact. Last year, Bonamy, Perrett and I proved that a fraction of 1/26 away from the upper bound holds for large enough maximum degree. In this talk, we show using new techniques that the list-coloring versions of these results hold, namely that there is such a convex combination for which the statement holds for the list chromatic number. Furthermore, we show that for large enough maximum degree, a fraction of 1/13 suffices for the list chromatic number, improving also on the bound for ordinary chromatic number. This is joint work with Michelle Delcourt.

Mohit Singh
Nash Social Welfare, Permanents and Inequalities on Stable Polynomials

Abstract: Given a collection of items and agents, Nash social welfare problem aims to find a fair assignment of these items to agents. The Nash social welfare objective is to maximize the geometric mean of the valuation of the agents in the assignment. In this talk, we will give a new mathematical programming relaxation for the problem and give an approximation algorithm based on a simple randomized algorithm. To analyze the algorithm, we find new connections of the Nash social welfare problem to the problem of computation of permanent of a matrix. A crucial ingredient in this connection will be new inequalities on stable polynomials that generalize the work of Gurvits. Joint work with Nima Anari, Shayan Oveis-Gharan and Amin Saberi.

Open Problems

There are two. One is, will we be snowed in or snowed out this Monday? The other is, can some of the open problem raised by these talks be solved?