Georgia Institute of Technology College of Sciences

Consider a random coloring of a bounded domain in the bipartite graph Z^d with the probability of each color configuration proportional to exp(-beta*N(F)), where beta>0, and N(F) is the number of nearest neighboring pairs colored by the same color. This model of random colorings biased towards being proper, is the antiferromagnetic 3-state Potts model from statistical physics, used to describe magnetic interactions in a spin system. The Kotecky conjecture is that in such a model with d >= 3, Fixing the boundary of a large even domain to take the color $0$ and high enough beta, a sampled coloring would typically exhibits long-range order. In particular a single color occupies most of either the even or odd vertices of the domain. This is in contrast with the situation for small beta, when each bipartition class is equally occupied by the three colors. We give the first rigorous proof of the conjecture for large d. Our result extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the zero beta=infinity case, where the coloring is chosen uniformly for all proper three-colorings. In the talk we shell give a glimpse into the combinatorial methods used to tackle the problem. These rely on structural properties of odd-boundary subsets of Z^d. No background in statistical physics will be assumed and all terms will be thoroughly explained.

We present an algebraic framework which simultaneously generalizes the notion of linear subspaces, matroids, valuated matroids, and oriented matroids. We call the resulting objects matroids over hyperfields. We give "cryptomorphic" axiom systems for such matroids in terms of circuits, Grassmann-Plucker functions, and dual pairs, and establish some basic duality theorems.

Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of $K_5$. This conjecture was proved by Ma and Yu for graphs containing $K_4^-$. Recently, we proved this entire Kelmans-Seymour conjecture. In this talk, I will give a sketch of our proof, and discuss related problems. This is joint work with Dawei He and Xingxing Yu.

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems (X,\Sigma), where each element x \in X lies in t randomly selected sets of \Sigma, where t \le |X| is an integer parameter. We provide new discrepancy bounds in this case. Specifically, we show that when |\Sigma| \ge |X| the hereditary discrepancy of (X,\Sigma) is with high probability O(\sqrt{t \log t}), matching the Beck-Fiala conjecture upto a \sqrt{\log{t}} factor. Our analysis combines the Lov{\'a}sz Local Lemma with a new argument based on partial matchings.