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

Question

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

Answer 1

The answer is negative. Suppose $3\le k\lt\omega$. As I showed in my answer to this question, there is a linear $k$-hypergraph $(\omega,E)$ with chromatic number $\aleph_0$; of course it can be extended to a maximal linear $k$-hypergraph on $\omega$, which will still have chromatic number $\aleph_0$. (By a $k$-hypergraph I mean a hypergraph whose edges are $k$-element sets.) I will now show how to construct a maximal linear $k$-hypergraph with chromatic number $2$.

Let $\omega=X\cup Y$ where $X$ and $Y$ are disjoint infinite sets. Choose sets $E\subseteq[X]^{k-1}$ and $F\subseteq[Y]^{k-1}$ so that $(X,E)$ and $(Y,F)$ are maximal linear $(k-1)$-hypergraphs. Enumerate the sets $E$ and $F$ without repetition as $E=\{e_n:n\in\omega\}$ and $F=\{f_n:n\in\omega\}$. For $n\in\omega$ choose recursively $x_n\in X\setminus(e_1\cup\cdots\cup e_n\cup\{x_1,\dots,x_{n-1}\})$ and $y_n\in Y\setminus(f_1\cup\cdots\cup f_n\cup\{y_1,\dots,y_{n-1}\})$. Let $\hat E=\{e_n\cup\{y_n\}:n\in\omega\}$ and $\hat F=\{f_n\cup\{x_n\}:n\in\omega\}$.

It can easily be verified that $\hat H=(\omega,\hat E\cup\hat F)$ is a linear $k$-hypergraph, and $\chi(H)=2$. Extend $\hat H$ to a maximal linear $k$-hypergraph $H$. (If $k=3$ then $E=[X]^2$, $F=[Y]^2$, and $\hat H$ is already maximal, so $H=\hat H$ in this case.) Because of the maximality of $E$ and $F$, each edge of $H$ meets both $X$ and $Y$, so $H$ is still $2$-colorable.

For a simple concrete example of a $2$-colorable maximal linear $3$-hypergraph, take $H=(\omega,E\cup F)$ where $$E=\{\{x,y,z\}\in[\omega]^3:x\ne y,\ x\equiv y\equiv0\pmod2,\ z=x+y+1\}$$ and $$F=\{\{x,y,z\}\in[\omega]^3:x\ne y,\ x\equiv y\equiv1\pmod2,\ z=x+y\}.$$