Random hypergraphs and property B

DOI10.1016/J.EJC.2020.103205MaRDI QIDQ2225409zbMATH OpenOpenAlexFDO

Authors Lech Duraj, Jakub Kozik, D. A. Shabanov

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.12968

zbMATH Keywords

algorithmic barrierefficient coloringrandom constraint satisfaction problems

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: In 1964 ErdH{o}s proved that $(1+oh1))fraceulln(2)4k^2{2}^k$ edges are sufficient to build a $k$-graph which is not two colorable. To this day, it is not known whether there exist such $k$-graphs with smaller number of edges. ErdH{o}s' bound is consequence of the fact that a hypergraph with $k^2/2$ vertices and $M(k)=(1+oh1)fraceulln(2)4k^2{2}^k$ randomly chosen edges of size $k$ is asymptotically almost surely not two colorable. Our first main result implies that for any $varepsilon>0$, any $k$-graph with $(1-varepsilon)M(k)$ randomly and uniformly chosen edges is a.a.s. two colorable. The presented proof is an adaptation of the second moment method analogous to the developments of Achlioptas and Moore from 2002 who considered the problem with fixed size of edges and number of vertices tending to infinity. In the second part of the paper we consider the problem of algorithmic coloring of random $k$-graphs. We show that quite simple, and somewhat greedy procedure, a.a.s. finds a proper two coloring for random $k$-graphs on $k^2/2$ vertices, with at most $Ohklnkcdot{2}^k$ edges. That is of the same asymptotic order as the analogue of the emph{algorithmic barrier} defined by Achlioptas and Coja-Oghlan in 2008, for the case of fixed $k$.

Recommendations

• Two‐coloring random hypergraphs
• On the 2-colorability of random hypergraphs
• Randomized algorithms for colourings of hypergraphs
• A note on two-colorability of nonuniform hypergraphs
• A note on random greedy coloring of uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3188524 (Why is no real title available?)
• A better algorithm for random \(k\)-SAT
• Catching the \(k\)-NAESAT threshold
• Improved bounds and algorithms for hypergraph 2-coloring
• On a combinatorial problem. II
• On the 2-colorability of random hypergraphs
• Panchromatic 3-colorings of random hypergraphs
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• The condensation transition in random hypergraph 2-coloring
• Two‐coloring random hypergraphs

Cited in

(5)

• A note on two-colorability of nonuniform hypergraphs
• How many random edges make a dense hypergraph non-2-colorable?
• On the 2-colorability of random hypergraphs
• Randomized algorithms for colourings of hypergraphs
• Two‐coloring random hypergraphs

This page was built for publication: Random hypergraphs and property B

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225409)