Existence of hypergraphs with large parameter values

Question

By a result of Erdös, proved using the probabilistic method, there exist graphs of arbitrarily large chromatic number and girth.

What are the corresponding results for hypergraphs (given some appropriate hypergraph notion of chromatic number and girth) and what is a good paper to look them up?

Answer 1

For this kind of problem, there are many open problems. I start with Erd\"os on Graphs by Chung and Graham, not because it is up to date (it's 17 years old), but because it has many references and necessary keywords. Hypergraph chromaticity is section 6.6 there. There I find that

• 3-chromatic 2-graphs require 3 edges ($m_2(2) = 3$, in the notation there),
• 3-chromatic 3-graphs require 7 edges ($m_2(3) = 7$), and
• the smallest number of edges that a 3-chromatic 4-graph can have is between 21 and 23 ($12 \leq m_2(4) \leq 23$).

These were reported by G. Manning (The $M(4)$ Problem of Erd\"os and Hajnal, 1997) and M.K. Goldberg and H.C.Russell (Toward computing $m(4)$, 1995). These suggest checking their authors for pulications involving "m(" and "M(". Searching for such things, we find J. Mathews, et al. (On the construction of non-2-colorable uniform hypergraphs, 2014) reporting improvements up to $m_2(8)$.

The short answer seem to be that there is not much known about $m_k(r)$ for $k \geq 2$ and $r > 2$ (and even the complement of this set is mostly terra incognita). Other references potentially useful to you:

• Greene, Chromatic capacities of graphs and hypergraphs, 2004,
• Caro, et al., Selective Hypergraph Colourings, 2015
• Kostochka and R\"odl, Constructions of Sparse Uniform Hypergraphs With High Chromatic Number, 2010 (includes girth results),
• Wagner, Generalized Girth Problems in Graphs and Hypergraphs, 2013

Good luck. (Solve all our problems. :-) )