2
$\begingroup$

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$?

$\endgroup$
1
  • $\begingroup$ Can you show from your probabilistic argument how to construct a $2$-coloring on a given rainbow hypergraph? $\endgroup$ Commented Feb 10, 2021 at 12:25

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$ Commented Feb 10, 2021 at 14:16
  • $\begingroup$ 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? $\endgroup$ Commented Feb 10, 2021 at 14:21
  • $\begingroup$ Thank you very much for editing your answer - I appreciate it and accepted it. $\endgroup$ Commented Feb 11, 2021 at 7:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .