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

英文解析

35. [ 25 ] An independent set of a graph G is a set of vertices of G such that no two vertices among theseare connected by an edge. If G has 2000 vertices, and each vertex has degree 10, find the maximumpossible number of independent sets that G can have.
    Answer: 2047100
    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 thebest bound.
    This problem received considerable attention due to its application to combinatorial group theory andstatistical mechanics, but no solution was found until 2009, when Yufei Zhao resolved Alon’s conjecturewith 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 hispaper “The Number of Independent Sets in a Regular Graph” available on his website athttp://web.mit.edu/yufeiz/www/indep reg.pdf .