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 Erdos, 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 (7)n≈2.65n 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.