The binomial random-subset independence conjecture
Statement
For a graph , let be its maximum independent-set density. Let be a binomial random subset of , with each vertex included independently with probability , and let
For , define
Binomial random-subset independence conjecture. There exists a monotone non-decreasing function , positive throughout its domain, such that if has maximum independent-set size , then
where is a maximum independent set contained in . 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.