Skip to main content
2 of 2
Added top-level tag
gmvh
  • 3.1k
  • 6
  • 27
  • 45

Chromatic number of maximal linear $k$-regular hypergraphs on $\omega$

For any integer $k>1$ we say a hypergraph $H=(\omega,E)$ where $E\subseteq {\cal P}(\omega)$ is $k$-regular if $|e|=k$ for all $e\in E$. Moreover, we say $H$ is linear if $|e_1\cap e_2|\leq 1$ for all $e_1\neq e_2 \in E$.

Zorn's lemma shows that whenever $(\omega,E)$ is linear and $k$-regular, there is $E'\supseteq E$ such that $(\omega,E')$ has the same properties and is maximal with respect to $k$-regularity and linearity (that is, whenever $e\in [\omega]^k\setminus E'$ we have that $(\omega, E'\cup \{e\})$ is no longer linear, where $[\omega]^k$ denotes the collection of subsets of $\omega$ with cardinality $k$).

If $\kappa>0$ is a cardinal and $H=(V,E)$ we say $c:V\to \kappa$ is a (hypergraph) colouring if the restriction $c\restriction_e$ is non-constant whenever $e\in E$ and $|e|>1$. The smallest cardinal $\kappa$ such that there is a colouring $c:V\to \kappa$ is called the chromatic number of $H$ and denoted by $\chi(H)$.

Question. Whenever $(\omega, E_1)$ and $(\omega,E_2)$ are $k$-regular for $k>2$ and maximal linear, do we have $\chi(\omega,E_1)= \chi(\omega,E_2)$?