Hard-core Caro–Wei conjecture

For λ>0\lambda>0, define

fλ(d)=λ1+(d+1)λ.f_\lambda(d)=\frac{\lambda}{1+(d+1)\lambda}.

Let G=(V,E)G=(V,E) be a graph, and let XX be a random independent set chosen from the hard-core model at fugacity λ\lambda.

Hard-core Caro–Wei conjecture. The expected size of XX satisfies

EXvVfλ(deg(v)).\mathbb{E}|X|\ge\sum_{v\in V}f_\lambda(\deg(v)).

This would strengthen the average-degree occupancy bound, remain sharp for disjoint unions of complete graphs, and refine the Caro–Wei theorem and a related lower bound on the hard-core partition function.

Sources & referencesView supporting material

Primary source

Ewan Davies and Ross J. Kang, “The hard-core model in graph theory”, arXiv:2501.03379 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.