• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Random hypergraphs and property B

European Journal of Combinatorics. 2021. Vol. 91. P. 1-11.
Shabanov D. A., Kozik J., Duraj L.

In 1964 Erdos proved that $(1+\oh{1})) \frac{\eul \ln(2)}{4} k^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.
Erd\H{o}s' bound is consequence of the fact that a hypergraph with $k^2/2$ vertices and $M(k)=(1+\oh{1}) \frac{\eul \ln(2)}{4} k^2 2^{k}$ randomly chosen edges of size $k$ is not two colorable with high probability.
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 coloring for random $k$-graphs on $k^2/2$ vertices, with at most $\Oh{k\ln k\cdot 2^k}$ edges. That value coincides with the analogue of algorithmic barrier defined by Achlioptas and Coja-Oghlan in 2008, for the case of fixed $k$.