Return to Answer

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\equiv y\equiv0\pmod2,\ x\ne y,\ z=x+y+1\}$$ and $$F=\{\{x,y,z\}\in[\omega]^3:x\equiv y\equiv1\pmod2,\ x\ne y,\ z=x+y\}.$$

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

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\equiv y\equiv0\pmod2,\ x\ne y,\ z=2^{x+y}+1\}$$ and $$F=\{\{x,y,z\}\in[\omega]^3:x\equiv y\equiv1\pmod2,\ x\ne y,\ z=2^{x+y}\}.$$

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\equiv y\equiv0\pmod2,\ x\ne y,\ z=x+y+1\}$$ and $$F=\{\{x,y,z\}\in[\omega]^3:x\equiv y\equiv1\pmod2,\ x\ne y,\ z=x+y\}.$$

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.

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\equiv y\equiv0\pmod2,\ x\ne y,\ z=2^{x+y}+1\}$$ and $$F=\{\{x,y,z\}\in[\omega]^3:x\equiv y\equiv1\pmod2,\ x\ne y,\ z=2^{x+y}\}.$$