HMMT 二月 2011 · 冲刺赛 · 第 35 题

HMMT February 2011 — Guts Round — Problem 35

[ 25 ] An independent set of a graph G is a set of vertices of G such that no two vertices among these are connected by an edge. If G has 2000 vertices, and each vertex has degree 10, find the maximum possible number of independent sets that G can have.

解析

[ 25 ] An independent set of a graph G is a set of vertices of G such that no two vertices among these are connected by an edge. If G has 2000 vertices, and each vertex has degree 10, find the maximum possible number of independent sets that G can have. 100 Answer: 2047 The upper bound is obtained when G is a disjoint union of bipartite graphs, each of which has 20 vertices with 10 in each group such that every pair of vertices not in the same group are connected. In 1991, during his study of the Cameron—Erdos conjecture on the number of sum-free sets, Noga Alon came across this problem on independent sets and conjectured that our construction gives the best bound. This problem received considerable attention due to its application to combinatorial group theory and statistical mechanics, but no solution was found until 2009, when Yufei Zhao resolved Alon’s conjecture with a beautiful and elementary approach. For the reader to enjoy the full insight of Yufei’s argument, we omit the proof here and refer to his paper “The Number of Independent Sets in a Regular Graph” available on his website at http://web.mit.edu/yufeiz/www/indep reg.pdf .