Let $X\neq\emptyset$ be a set. A family ${\cal S}\subseteq {\cal P}(X)$ has property $\mathbf{B}$ if there is $T\subseteq X$ such that for all $S\in{\cal S}$ we have $S\cap T\neq \emptyset$ and $S\not\subseteq T$. Moreover, ${\cal S}$ is said to be linear if $|S_1 \cap S_2| \leq 1$ for all $S_1\neq S_2\in{\cal S}$.

Let $\text{FL}(\omega)$ be the collection of linear families ${\cal S}$ of $\omega$ such that all $S\in{\cal S}$ are finite and have at least $2$ elements. A standard application of Zorn's Lemma shows that every member of $\text{FL}(\omega)$ is contained in a member of $\text{FL}(\omega)$ that is maximal with respect to set inclusion.

Question. Is there a maximal member of $\text{FL}(\omega)$ which has property ${\bf B}$?


1 Answer 1


Yes. Partition $\omega$ into two disjoint infinite subsets $T_1$ and $T_2$. Recursively construct a $3$-uniform linear hypergraph (Steiner triple system) $\mathcal S\subseteq\binom\omega3$ so that each element of $\binom\omega2$ is contained in a unique element of $\mathcal S$, and each element of $\mathcal S$ meets both $T_1$ and $T_2$. Namely, we enumerate the elements of $\binom\omega2$, and when we come to an element $\{x,y\}$ of $\binom\omega2$ which is not already covered, choose $i\in\{1,2\}$ so that $\{x,y\}\not\subseteq T_i$ and choose a number $z\in T_i\setminus\{x,y\}$ which is not in any element of $\binom\omega3$ which has already been put into $\mathcal S$, and add the triple $\{x,y,z\}$ to $\mathcal S$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .