On the construction of 3-chromatic hypergraphs with few edges

The minimum number m(n) of edges in a 3-chromatic n-uniform hypergraph has been widely studied in the literature. The best known upper bound is due to Erdős, who showed, using the probabilistic method, that m(n)⩽O(n22n). Abbott and Moser gave an explicit construction of a 3-chromatic n-uniform hypergraph with at most hyperedges, which is the best known constructive upper bound. In this paper we improve this bound to 2(1+o(1))n. Our technique can also be used to describe n-uniform hypergraphs with chromatic number at least r+1 and at most r(1+o(1))n hyperedges, for every r⩾3.