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

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

1 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\}.$$

  • $\begingroup$ That's amazing with your maximal linear hypergraph of chromatic number $2$! $\endgroup$ Mar 14, 2021 at 7:55

Your Answer

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

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