On the average size of independent sets in triangle-free graphs

NEW

Problem: Reconstructed statement: for every finite triangle-free graph $G$ with minimum degree $d$, if

is the average size of a uniformly random independent set, then

This is the stated Conjecture 2 from Davies–Jenssen–Perkins–Roberts.

Result: The conjecture is false.

Let

the Cartesian product of the 5-cycle and the complete bipartite graph $K_{m,m}$. Both factors are triangle-free, and the Cartesian product of triangle-free graphs is triangle-free. Also $G_m$ is $(m+2)$-regular, so its minimum degree is $d=m+2\to\infty$.

Each fibre over a vertex of $K_{m,m}$ is a copy of $C_5$, so an independent set contains at most $2$ vertices in each such fibre. Since $K_{m,m}$ has $2m$ vertices,

Equality holds: choose two disjoint independent pairs in $C_5$, one for all vertices on the left side of $K_{m,m}$ and one for all vertices on the right side. Hence

Now count independent sets. An independent set of $G_m$ assigns to each vertex of $K_{m,m}$ an independent subset of $C_5$, with the condition that states assigned to adjacent vertices of $K_{m,m}$ are disjoint.

Let $\mathcal S=\mathcal I(C_5)$. For compatible families $A,B\subseteq\mathcal S$, meaning every $S\in A$ is disjoint from every $T\in B$, the exponential contribution is $|A|^m|B|^m$. The maximum of $|A||B|$ is $24$, achieved when one side is all independent subsets of a nonadjacent pair in $C_5$, giving $4$ states, and the other side is all independent subsets of the complementary induced edge-plus-isolated-vertex subgraph, giving $6$ states.

For these dominant patterns, the mean state size on the two sides is

All other compatible patterns have strictly smaller exponential base, so

Therefore

Thus the claimed lower bound $2-o_d(1)$ fails even for regular triangle-free graphs.

Citation: Original conjecture: E. Davies, M. Jenssen, W. Perkins, B. Roberts, “On the average size of independent sets in triangle-free graphs,” Proc. Amer. Math. Soc. 145 (2017), 3543–3555.