# Chromatic number of rainbow hypergraphs

Let $$H=(V,E)$$ be a hypergraph, and $$\kappa$$ be a cardinal. We say that a map $$c:V \to \kappa$$ is a coloring if the restriction $$c\restriction_e$$ is non-constant whenever $$e\in E$$ and $$|e|\geq 2$$. The smallest cardinal $$\kappa$$ such that there is a coloring $$c:V\to\kappa$$ is said to be the chromatic number of $$H$$, and we denote it by $$\chi(H)$$.

Let $$\omega$$ denote the set of non-negative integers. We say that a hypergraph $$H=(\omega,E)$$ is a rainbow hypergraph if every member of $$E$$ is finite, and if for every $$n\in\omega\setminus\{0,1\}$$ there is exactly one $$e\in E$$ with $$|e|=n$$ (that is, for all $$n\in\omega\setminus\{0,1\}$$ we have $$|\{e\in E: |e| = n\}|=1$$).

There are many rainbow hypergraphs with chromatic number $$2$$ (for instance, any hypergraph in which the edges are pairwise disjoint.)

Question. Given $$k\in (\omega\cup\{\omega\})\setminus \{0,1\}$$, is there a rainbow hypergraph $$H=(\omega,E)$$ with $$\chi(H)=k$$?

• Can you show from your probabilistic argument how to construct a $2$-coloring on a given rainbow hypergraph? – Dominic van der Zypen Feb 10 at 12:25

In fact, every rainbow hypergraph has chromatic number $$2$$.
Let $$H=(V,E)$$ be a rainbow hypergraph, $$E=\{e_2,e_3,\dots\}$$, $$|e_n|=n$$. Consider a random coloring $$c:V\to\{0,1\}$$, let $$A$$ be the event that $$c$$ is not a proper coloring of $$H$$, and let $$A_n$$ be the event that $$c$$ is constant on $$e_n$$. Then $$P(A)=P\left(\bigcup_{n=2}^\infty A_n\right)\lt\sum_{n=2}^\infty P(A_n)=\sum_{n=2}^\infty\frac1{2^{n-1}}=1,$$ so proper $$2$$-colorings exist and $$\chi(H)=2$$.
P.S. Here is an alternative argument which even proves a slightly stronger result: a rainbow graph remains $$2$$-colorable if one more edge is added arbitrarily.; i.e., there are now two edges of size $$2$$ and one edge of size $$n$$ for each integer $$n\gt2$$.
Let $$H=(V,E)$$ be a hypergraph, $$E=\{e_1,e_2,e_3,\dots\}$$ where $$|e_n|=\max(n,2)$$. We color the vertices sequentially, coloring $$2$$ vertices at each step, one red and the other blue; this is done in such a way that after the $$n^\text{th}$$ step is completed (if not sooner) the edge $$e_n$$ contains at least one vertex of each color. This can always be done, unless the elements of $$e_n$$ have all been given the same color before the $$n^\text{th}$$ step; but that can't happen because $$|e_n|\ge n$$ and each color has only been used $$n-1$$ times before the $$n^\text{th}$$ step.
• Thanks for expanding your comment into an answer. I am uneasy about "events", how can we put a probability measure $P$ on the set of maps $c:\omega \to \{0,1\}$ (let's call this set $2^\omega$)? So I assume $A\subseteq 2^\omega$ is the collection of functions $c\in 2^\omega$ such that $c$ is not a proper coloring of the rainbow hypergraph $H$. I would be happy to know $A \neq 2^\omega$, but you appear to prove something stronger: $P(A)<1$, but how do you define $P$? – Dominic van der Zypen Feb 10 at 14:16
• To make things more precise: I would be glad if you can define the $\sigma$-algebra ${\cal A}$ on $2^\omega$ you consider, as well as the probability measure $P:{\cal A}\to [0,1]$. Then we have to establish $A \in {\cal A}$ where $A$ is the collection of non-colorings of the rainbow hypergraph $H$. - Or am I completely off the track? – Dominic van der Zypen Feb 10 at 14:21