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

• The chromatic number can be infinite, so the question reduces to whether it will always be infinite. Mar 13, 2021 at 22:16
• Please change "regular" to "uniform".
– bof
Mar 13, 2021 at 23:25

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\}.$$
• That's amazing with your maximal linear hypergraph of chromatic number $2$! Mar 14, 2021 at 7:55