The fugacity-uniform triangle-free average-to-maximum ratio conjecture

About 10 years old · traced to

Let GG be a triangle-free graph. For 4λ>044\lambda>04, let 4α‾G(λ)44\overline{\alpha}_G(\lambda)4 denote the average size of an independent set in the hard-core model at fugacity 4λ44\lambda4, and let 4α(G)44\alpha(G)4 be the maximum independent set size.

Fugacity-uniform ratio conjecture. For every 4ϵ>044\epsilon>04, there exists 4λ>044\lambda>04 such that, for every triangle-free graph GG,

α(G)α‾G(λ)≥2−ϵ.\frac{\alpha(G)}{\overline{\alpha}_G(\lambda)} \ge 2-\epsilon.

This would yield the same asymptotic improvement to the upper bound on R(3,k)R(3,k) as the minimum-degree conjecture. Its status is not resolved in the supplied text.

References

Primary source

Ewan Davies, Matthew Jenssen, Will Perkins and Barnaby Roberts, “On the average size of independent sets in triangle-free graphs”, arXiv:1606.01043 (2017).

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.