Georgia Institute of Technology College of Sciences

We study an old problem of Linial and Wilf to find the graphs with n vertices and m edges which maximize the number of proper q-colorings of their vertices. In a breakthrough paper, Loh, Pikhurko and Sudakov asymptotically reduced the problem to an optimization problem. We prove the following structural result which tells us how the optimal solutionlooks like: for any instance, each solution of the optimization problem corresponds to either a complete multipartite graph or a graph obtained from a complete multipartite graph by removing certain edges. We then apply this result on optimal graphs to general instances, including a conjecture of Lazebnik from 1989 which asserts that for any q>=s>= 2, the Turan graph T_s(n) has the maximum number of q-colorings among all graphs with the same number of vertices and edges. We disprove this conjecture by providing infinity many counterexamples in the interval s+7 <= q <= O(s^{3/2}). On the positive side, we show that when q= \Omega(s^2) the Turan graph indeed achieves the maximum number of q-colorings. Joint work with Humberto Naves.

Abstract: There has been a recent flurry of interest in the spectral theory of tensors and hypergraphs as new ideas have faithfully analogized spectral graph theory to uniform hypergraphs. However, even in their simplest incarnation -- the homogeneous adjacency spectrum -- a large number of seemingly basic questions about hypergraph spectra remain out of reach. One of the problems that has yet to be resolved is the (asymptotically almost sure) spectrum of a random hypergraph in the Erd\H{o}s-R\'{e}nyi sense, and we still don't know the spectrum of complete hypergraphs (other than a kind of implicit description for 3-uniform). We introduce the requisite theoretical framework and discuss some progress in this area that involves tools from commutative algebra, eigenvalue stability, and large deviations.

Sidorenko's conjecture states that the number of homomorphisms from a bipartite graph $H$ to a graph $G$ is at least the expected number of homomorphisms from $H$ to the binomial random graph with the same expected edge density as $G$. In this talk, I will present two approaches to the conjecture. First, I will introduce the notion of tree-arrangeability, where a bipartite graph $H$ with bipartition $A \cup B$ is tree-arrangeable if neighborhoods of vertices in $A$ have a certain tree-like structure, and show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices $a_1, a_2$ in $A$ such that each vertex $a \in A$ satisfies $N(a) \subseteq N(a_1)$ or $N(a) \subseteq N(a_2)$. Second, I will prove that if $T$ is a tree and $H$ is a bipartite graph satisfying Sidorenko's conjecture, then the Cartesian product of $T$ and $H$ also satisfies Sidorenko's conjecture. This result implies that, for all $d \ge 2$, the $d$-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture. Joint work w/ Jeong Han Kim (KIAS) and Joonkyung Lee (Oxford).

The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much nicer properties. In this talk we discuss smoothed analysis on trees, or equivalently on connected graphs. A connected graph G on n vertices can be a very bad expander, can have very large diameter, very high mixing time, and possibly has no long paths. The situation changes dramatically when \eps n random edges are added on top of G, the so obtained graph G* has with high probability the following properties: - its edge expansion is at least c/log n; - its diameter is O(log n); - its vertex expansion is at least c/log n; - it has a linearly long path; - its mixing time is O(log^2n) All of the above estimates are asymptotically tight. Joint work with Michael Krivelevich (Tel Aviv) and Wojciech Samotij (Tel Aviv/Cambridge).