Maximum-to-Average Independence Ratios in Triangle-Free Graphs

Definitions and mathematical statement

For the formulation below, let $G=(V,E)$ be a finite, nonempty, simple undirected graph. These graph conventions are needed to make the stated ratio precise but are not explicitly specified in the supplied record. Say that $G$ is triangle-free if no three distinct vertices are pairwise adjacent. Define \[ \mathcal I(G)=\{S\subseteq V: \text{no edge of }G\text{ has both endpoints in }S\}, \qquad \alpha(G)=\max_{S\in\mathcal I(G)}|S|. \] Here $\mathcal I(G)$ includes the empty independent set. If $I$ is chosen uniformly from $\mathcal I(G)$, define \[ m(G)=\mathbb E|I|=\frac{\sum_{S\in\mathcal I(G)}|S|}{|\mathcal I(G)|}, \qquad R(G)=\frac{\alpha(G)}{m(G)}. \] Since $V\ne\varnothing$, one has $m(G)>0$. Let $\delta(G)=\min_{v\in V}\deg_G(v)$.

The supplied record asks the following two questions:

1. Does every such triangle-free graph satisfy \[ R(G)\ge \frac43? \]
2. Does there exist a function $\varepsilon:\mathbb Z_{\ge0}\to[0,\infty)$, with $\lim_{d\to\infty}\varepsilon(d)=0$, such that, for every integer $d\ge0$ and every such triangle-free graph $G$ with $\delta(G)=d$, \[ R(G)\ge 2-\varepsilon(d)? \]

The second formulation interprets the source notation $2-o_d(1)$ as a bound uniform over all graphs of minimum degree $d$. The finite simple graph convention, exclusion of the graph with no vertices, inclusion of the empty independent set in the averaging family, and uniform interpretation of the asymptotic term require confirmation against the original source.

Short English statement

The questions compare the largest independent set in a triangle-free graph with the mean size of an independent set chosen uniformly from all independent sets. They ask whether this ratio is always at least $4/3$, and whether it is at least $2-\varepsilon(d)$, uniformly over graphs of minimum degree $d$, for some $\varepsilon(d)\to0$. The graph and averaging conventions are stated explicitly and require source confirmation.

Sources

• Local UnsolvedMath registry, data/unsolvedmath/problems.json, supplied record with permanent ID $30003335$, source problem code catalogue entry, entitled "Maximum-to-Average Independence Ratios in Triangle-Free Graphs." The record gives proposed year 2017 and names no proposer.
• Supplied report citation: Combinatorics (2018), Oberwolfach Reports, DOI 10.4171/owr/2017/1, pp. 5--81. Original OWR report: https://doi.org/10.4171/owr/2017/1. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: Davies--Jenssen--Perkins--Roberts, "average independent sets," https://arxiv.org/abs/1606.01043.
• Supplied literature source: Davies--Kang, "hard-core model survey," https://arxiv.org/abs/2501.03379.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that average-size lower bounds and occupancy-fraction theory have advanced substantially, while the proposed $4/3$ ratio bound and the minimum-degree bound approaching $2$ remain unresolved. This is supplied dated literature triage derived from the OWR curation, not an independently verified assessment. The record requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports manual semantic, typographic, and LaTeX review. These are supplied editorial claims, not independent mathematical or source verification of this draft.