ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For a graph GG, let αˉ(G)\bar{\alpha}(G) be its maximum independent-set density. Let WW be a binomial random subset of V(G)V(G), with each vertex included independently with probability 1/21/2, and let

α∗∗(G)=EW[max⁡I∈I(G)μ(I∩W)].\alpha^{**}(G)=E_W\left[\max_{I\in{\cal I}(G)}\mu(I\cap W)\right].

For α∈(0,1/2)\alpha\in(0,1/2), define

ϵ∗∗(α)=inf⁡G: αˉ(G)≥α{αˉ(G)−α∗∗(G)}.\epsilon^{**}(\alpha)=\inf_{G:\,\bar{\alpha}(G)\geq\alpha}\{\bar{\alpha}(G)-\alpha^{**}(G)\}.

Binomial random-subset independence conjecture. There exists a monotone non-decreasing function ϵ∗∗:(0,1/2)→(0,1/2)\epsilon^{**}:(0,1/2)\to(0,1/2), positive throughout its domain, such that if GG has maximum independent-set size αn\alpha n, then

α∗∗(G)=EW[∣IW∣/n]≤α−ϵ∗∗(α),\alpha^{**}(G)=E_W[|I_W|/n]\leq\alpha-\epsilon^{**}(\alpha),

where IWI_W is a maximum independent set contained in WW. The source emphasizes that this remains open even for binomial vertex sampling, including the case in which every covering part consists of a single vertex.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.