2.2k citations · 3.3k across the 34 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
math.CO2020
On the 2-colorability of random hypergraphs
Dimitris Achlioptas, Cristopher Moore
A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let be a random -uniform hypergraph on vert…
cs.CC2020★ 13 cited
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky +2
We study the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We give formal evidence of average-cas…