  In 1964 Erd\H{o}s 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 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 $\Oh{k\ln k\cdot 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$.
