Let $X$ be an infinite set, and let ${\cal E}$ be a collection of non-empty subsets of $X$. We say that ${\cal E}$ has property $\mathbf{B}$ if there is $B\subseteq X$ such that $B\cap E\neq \emptyset$ and $E\not\subseteq B$ for all $E\in{\cal E}$. (This is equivalent to saying that the hypergraph $(X,{\cal E})$ has chromatic number $2$.)

It is possible to find a chain ${\frak E}$ (with respect to $\subseteq$) of collections with property $\mathbf{B}$ such that $\bigcup {\frak E}$ has not property ${\mathbf B}$ - but this does not imply that not every set of subsets of $X$ with property ${\mathbf B}$ is not in a maximal such set of subsets. This leads to the following:

Question. What is an example of a set $X$ and and set of non-empty subsets ${\cal E}$ of $X$ with property ${\mathbf B}$ such that ${\cal E}$ is not contained in a set of non-empty subsets ${\cal E'}$ of $X$ that is maximal with respect to having property ${\mathbf B}$ and set inclusion?


1 Answer 1


Any collection $\cal E$ satisfying property ${\mathbf B}$ (further: ${\mathbf B}$-collection) is contained in an inclusion-maximal ${\mathbf B}$-collection.

Proof: consider the corresponding 2-coloring of $\cal E$ and define the over-collection $\cal E_0$ as the collection of all sets which contain elements of both colors. It is easy to see that the 2-coloring for $\cal E_0$ is unique (sets of size 2 from $\cal E_0$ are enough for such a conclusion), therefore if we add any set to $\cal E_0$, it is no longer a ${\mathbf B}$-collection.


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.