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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.