Is it true that logn n E[χ(G(n, W ))] converges as n \to \infty?
Statement
Is it true that logn n E[χ(G(n, W ))] converges as n \to \infty? Resilience of perfect matchings in random hypergraphs Matthew Kwan Let Gk (n, p) be the Erdős–Rényi k-uniform random hypergraph with n vertices and edge probability p. Johansson, Kahn and Vu famously answered Shamir’s problem, showing that for any fixed constant k, if C is sufficiently large then whp G \sim Gk (n, C log n/nk−1 ) has a perfect matching. Asaf Ferber and I conjectured a resilience version of this theorem. A special case is the following: Conjecture: For any fixed constant k, if C is sufficiently large and \varepsilon > 0 is sufficiently small then whp G \sim Gk (n, C log n/nk−1 ) has the following property. Even if we adversarially delete (at most) an \varepsilon-fraction of the hyperedges at each vertex, G still has a perfect matching.
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.