Random hypergraphs and property B

DOI10.1016/J.EJC.2020.103205zbMATH Open1458.05237arXiv2102.12968OpenAlexW3082690547MaRDI QIDQ2225409FDOQ2225409

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

Publication date: 8 February 2021

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

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the 2-colorability of random hypergraphs
• Improved bounds and algorithms for hypergraph 2-coloring
• Title not available (Why is that?)
• On a combinatorial problem. II
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• A better algorithm for random \(k\)-SAT
• Catching the \(k\)-NAESAT threshold
• The condensation transition in random hypergraph 2-coloring
• Two‐coloring random hypergraphs
• Panchromatic 3-colorings of random hypergraphs

Cited In (5)

• 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
• A note on two-colorability of nonuniform 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)