Extremal regular graphs

This post is adapted from my new expository survey Extremal regular graphs: independent sets and graph homomorphisms.

The earliest result in extremal graph theory is usually credited to Mantel, who proved, in 1907, that a graph on {n} vertices with no triangles contains at most {n^2/4} edges, where the maximum is achieved for a complete bipartite graph with half of the vertices on one side and half on the other side. Much more is now known about the subject. While I initially encountered Mantel’s theorem as a high school student preparing for math contests, my first in-depth exposure to extremal graph theory was from taking a course by David Conlon during my year reading Part III at Cambridge (one can find excellent course notes on his website).

We seem to know less about sparse graphs (a general mantra in combinatorics, it seems). Let us focus on {d}-regular graphs, which are graphs where every vertex has degree {d}.

C4

The cycle of length 4 has a total of 7 independent sets.

An independent set in a graph is a subset of vertices with no two adjacent. Many combinatorial problems can be reformulated in terms of independent sets by setting up a graph where edges represent forbidden relations.

Question. In the family of {d}-regular graph of the same size, which graph has the most number of independent sets?

This question was raised by Andrew Granville in the 1988 Number Theory Conference at Banff, in an effort to resolve a problem in combinatorial number theory, namely the Cameron–-Erdős conjecture on the number of sum-free sets. The question appeared first in print in a paper by Noga Alon, who proved an asymptotic upper bound and speculated that, at least when {n} is divisible by {2d}, the maximum should be attained by a disjoint union of complete bipartite graphs {K_{d,d}}.

Some ten years later, Jeff Kahn arrived at the same conjecture while studying a problem arising from statistical physics. Using a beautiful entropy argument, Kahn proved the conjecture under the additional assumption that the graph is already bipartite.

Fast forward another nearly ten years. In the summer of 2009, during my last summer as an undergraduate, I spent a fun and productive summer attending Joe Gallian’s REU in Duluth, MN (a fantastic program, by the way!), and there I showed that Kahn’s theorem can be extended to all regular graphs, not just bipartite ones.

Here is the theorem statement. We write {I(G)} to denote the set of independent sets in {G}, and {i(G) := |I(G)|} the number of independent sets in {G}.

Theorem (Kahn, Z.) If {G} is an {n}-vertex {d}-regular graph, then

\displaystyle i(G) \le i(K_{d,d})^{n/(2d)} = (2^{d+1} - 1)^{n/(2d)}.

In the survey, I provide an exposition of the proofs of these two theorems as well as a discussion of subsequent developments. Notably, Davies, Jenssen, Perkins, and Roberts recently gave a brand new proof of the above theorems by introducing a powerful new technique, called the occupancy method, inspired by ideas in statistical physics, and it already has a number of surprising new consequences.

On a personal level, I am pleased to see this topic gaining renewed interest. (Also, somewhat to my chagrin, my undergraduate paper, according to Google Scholar, still remains my most cited paper to date.)

I shall close this blog post with one of my favorite open problems in this area.

Let {c_q(G)} denote the number of proper {q}-colorings of {G}, i.e., coloring the vertices of {G} with {q} colors, so that no two adjacent vertices receive the same color.

Conjecture. If {G} is an {n}-vertex {d}-regular graph, and {q \ge 3}, then

\displaystyle c_q(G) \le c_q(K_{d,d})^{n/(2d)}.

I was pleased to learn from Will Perkins, who gave a talk at Oxford last week, that he, along with Davies, Jenssen, and Roberts, recently proved the conjecture for 3-regular graphs. The proof uses the occupancy method that they developed earlier. The method is reminiscent of the flag algebra machinery developed by Razborov some ten years ago for solving extremal problems in dense graphs. The new method can be seen as some kind of “flag algebra for sparse graphs”. I find this development quite exciting, and I expect that more news will come.

hom_coloring.png

Graph homomorphisms from G to K_q correspond to proper colorings of vertices of G with q colors.