Folklore conjecture on pseudorandom hypergraphs and the shattering threshold
Folklore conjecture on pseudorandom hypergraphs and the shattering threshold
A pseudorandom class of hypergraphs is a hereditary class whose sparse random model contains, with high probability, an induced subhypergraph on at least vertices belonging to the class. Let the shattering threshold be the size threshold at which the solution space of independent sets in a sparse random -uniform hypergraph fractures into exponentially many clusters. Folklore conjecture. There exists a pseudorandom class of hypergraphs whose independence number matches the shattering threshold. This is known for various pseudorandom graph classes, but had remained largely unexamined for higher uniformities; the paper states that uncrowded -uniform hypergraphs resolve the question affirmatively for every .
Sources & referencesView supporting material
Primary source
Abhishek Dhawan, Abhishek Methuku and Minh-Quan Vo, “The independence number of uncrowded hypergraphs: bounds matching the shattering threshold”, arXiv:2606.18048 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.