Refinement-minimal intersecting covers

Question

Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations. I wondered whether in general it was possible to minimize the intersections in a fictitious train network in which all lines intersected.

Formalization. Let $X\neq \emptyset$ be a set. We say ${\cal C}\subseteq {\cal P}(X)$ is a cover if $\bigcup {\cal C} = X$, and it is intersecting if whenever $A,B\in{\cal C}$ then $A\cap B \neq \emptyset$.

If ${\cal C}, {\cal D} \subseteq {\cal P}(X)$, we say ${\cal C}$ refines ${\cal D}$, or ${\cal C} \preceq {\cal D}$, if for all $C \in {\cal C}$ there is $D\in {\cal D}$ with $C\subseteq D$. Note that $\preceq$ is reflexive and transitive, but not anti-symmetric in general.

We say that an intersecting cover ${\cal C}_0$ is refinement-minimal if whenever ${\cal C}$ is an intersecting cover with ${\cal C} \preceq {\cal C}_0$, then ${\cal C}_0\preceq {\cal C}$.

Question. If $X$ is a non-empty set and ${\cal C} \subseteq {\cal P}(X)$ is an intersecting cover of $X$, is there necessarily an intersecting cover ${\cal C}_0\preceq {\cal C}$ such that ${\cal C}_0$ is refinement-minimal?

Answer 1

Let us recall that $\mathfrak u$ is the smallest cardinality of a base of a free ultrafilter on $\omega$. It is known (and easy to see) that $\omega_1\le\mathfrak u\le\mathfrak c$.

Example. There exists an intersecting cover $\mathcal C$ of a set $X$ of cardinality $|X|=\mathfrak u$ such that every intersecting cover $\mathcal C_0$ of $X$ with $\mathcal C_0\preceq \mathcal C$ is not refinement-minimal.

Proof. Take any free ultrafilter $\mathcal U$ on $\omega$ with base $\mathcal B$ of cardinality $|\mathcal B|=\mathfrak u$. Consider the set $X=\omega\cup\mathcal B$ and observe that $\mathcal C:=\{\{B\}\cup B:B\in\mathcal B\}$ is an intersecting cover of $X$.

Now take any intersecting cover $\mathcal C_0$ of $X$ with $\mathcal C_0\preceq \mathcal C$.

Claim 1. For every set $C\in\mathcal C_0$, the set $C\cap \omega$ belongs to the ultrafilter $\mathcal U$.

Proof. In the opposite case, the set $\omega\setminus C$ belongs to the ultrafilter $\mathcal U$. Since $\mathcal C_0\preceq\mathcal C$, there exists a set $B\in\mathcal B$ such that $C\subseteq \{B\}\cup B$. Since $\omega\setminus C\in\mathcal U$ and $B\in\mathcal B\subseteq\mathcal U$, there exists a set $B'\in\mathcal B\setminus\{B\}$ such that $B'\subseteq B\setminus C$. Since $\mathcal C_0$ is a cover of $X=\mathcal B\cup\omega$, there exists an element $C'\in\mathcal C_0$ such that $B'\in C'$. Since $\mathcal C_0\preceq \mathcal C$, there exists a set $B''\in\mathcal B$ such that $B'\in C'\subseteq \{B''\}\cup B''$, which implies that $B''=B'$ and hence $C'\subseteq \{B'\}\cup B'$ and $$C\cap C'\subseteq C\cap (\{B\}\cup B)\cap (\{B'\}\cup B')=C\cap B\cap B'\subseteq C\cap (B\setminus C)=\emptyset,$$ which contradicts the intersection property of the family $\mathcal C_0$. $\quad\square$

Now take any set $B\in\mathcal B$ and consider the subfamily $\mathcal C_B:=\{C\in\mathcal C_0:B\in C\}$.

Claim 2. For every $C\in\mathcal C_B$ we have $B\in C\subseteq \{B\}\cup B$.

Proof. Since $\mathcal C_0\preceq \mathcal B$, there exists a set $B'\in\mathcal B$ such that $B\in C\subseteq\{B'\}\cup B'$, which implies $B=B'$ and hence $B\in C\subseteq \{B\}\cup B$. $\quad\square$

Choose any set $C'\in\mathcal C_B$ and consider the set $U':=\omega\cap\bigcup\mathcal C_B$, which belongs to the ultrafilter $\mathcal U$, by Claim 1. Choose a base $\mathcal D$ of the ultrafilter $\mathcal U':=\{U'\cap U:U\in\mathcal U\}$ such that $U'=\bigcup\mathcal D$, $\mathcal D\preceq\mathcal C_B$, but $C'\setminus\{B\}\not\subseteq D$ for every $D\in\mathcal D$. Consider the family $$\mathcal C'_0:=(\mathcal C_0\setminus\mathcal C_B)\cup\{\{B\}\cup D:D\in\mathcal D\}.$$ It is easy to see that $\mathcal C_0'$ is an intersecting cover of $X$ such that $\mathcal C_0'\preceq\mathcal C_0$. Assuming that $\mathcal C_0\preceq\mathcal C_0'$, we can find a set $D\in\mathcal D$ such that $C'\subseteq\{D\}\cup D$ and hence $C'\setminus\{B\}\subseteq D$, which contradicts the choice of the base $\mathcal D$. This contradiction shows that the intersecting cover $\mathcal C_0$ is not refinement-minimal. $\quad\square$

The above Example motivates the following problem (of exchange the uncountable cardinal $\mathfrak u$ by the cardinal $\omega$):

Problem. Is there an intersecting cover without refinement-minimal refinements on a countable set?

Answer 2

Disclaimer: This is not an answer, and just too long for a comment.

Here is an example why the chain condition does not hold (which does not mean that there are no refinement-minimal covers, just that Zorns lemma cant be used to construct them. It might be interesting to check by hand what happens for this cover.

Let $X=\{a,b\}\cup \mathbb{N}$ with cover $\{A,B\}$ with $A=\{a\}\cup \mathbb{N}$,$B=\{b\}\cup \mathbb{N}$. Let $A_i= \{a\}\cup \{i,...\}$. Then $\{A_{i+1},B\}$ is a refinement of $\{A_i,B\}$ and so we have a chain.

Suppose we had a cover $\mathcal{C}$ with $\mathcal{C}\le \{A_i,B\}$ for all $i$. Let $C\in \mathcal{C}$ be a set containing $a$ and thus $C$ cannot be a subset of $B$. By definition of the covers, we have $C\subset A_i$ for all $i$ and thus $C=\{a\}$. Hence $C$ and $B$ do not intersect and thus $\mathcal{C}$ cannot be intersecting.

However the given cover has a refinement-minimal intersecting cover. For example the collection of all subsets containing $0$ and not containing both $\{a,b\}$ should be one (if I am not mistaken).

I think this makes the poset quite interesting. It has minimal elements, but the chain condition from Zorns lemma does not hold.

Answer 3

This is not even a partial answer, just an oversized comment. I consider only the special case where the set $X$ is countable and the intersecting cover $\mathcal C$ consists of finite sets. I am not able to settle even this special case, but I would like to record some equivalences which might be useful in settling it.

Let $\mathbf F$ be the set of all intersecting covers of $\mathbb N$ consisting of finite sets.

Lemma. For any $\mathcal C\in\mathbf F$ there exists $\mathcal C_1\in\mathbf F$ such that $\mathcal C_1\preceq\mathcal C$ and $\mathcal C_1$ is an antichain (no element of $\mathcal C_1$ is a subset of another).

Proof. Let $\mathcal M$ be the set of all minimal elements of $\mathcal C$ and let $\mathcal C_0=\{A\cup\{x\}:A\in\mathcal M,\ \{A\cup\{x\}\}\preceq C\}$. Then $\mathcal M\subseteq\mathcal C_0\preceq\mathcal C$ and $\mathcal C_0\in\mathbf F$. Let $\mathcal C_1$ be the set of all maximal elements of $\mathcal C_0$. Plainly $\mathcal C_1$ is an antichain and an intersecting family, and $\mathcal C_1\preceq\mathcal C$; I have to show that $\mathcal C_1$ covers $\mathbb N$. In fact I will show that there is no infinite chain in $\mathcal C_0$, whence every element of $\mathcal C_0$ is contained in a maximal element.

Assume for a contradiction that $\mathcal C_0$ contains an infinite chain $$A_1\cup\{x_1\}\subsetneqq A_2\cup\{x_2\}\subsetneqq A_3\cup\{x_3\}\subsetneqq\cdots$$ where $A_n\in\mathcal M$. Now $x_n\notin A_n$ for $n\ge2$, since $A_n\cup\{x_n\}\notin\mathcal M$ for $n\ge2$. Moreover, since $A_1\subseteq A_n\cup\{x_n\}$, while $A_1\not\subseteq A_n$ for $n\ge3$, we have $x_n\in A_1$ for $n\ge3$. Since $A_1$ is finite, by the pigeonhole principle we have $x_m=x_n=x$ for some $m,n$ with $3\le m\lt n$. But now, since $A_m\cup\{x\}\subsetneqq A_n\cup\{x\}$ and $x\notin A_m$, we have $A_m\subsetneqq A_n$, which is absurd.

Theorem. The following statements are equivalent:
(1) For any $\mathcal C\in\mathbf F$ there exists $\mathcal C'\in\mathbf F$, with $\mathcal C'\preceq\mathcal C$, such that $$\mathcal C'\succeq\mathcal B\in\mathbf F\implies\mathcal C'\preceq\mathcal B;$$ i.e., $\mathcal C'$ is refinement-minimal.
(2) For any $\mathcal C\in\mathbf F$ there exists $\mathcal C'\in\mathbf F$, with $\mathcal C'\preceq\mathcal C$, such that $$\mathcal C'\succeq\mathcal B\in\mathbf F\implies\mathcal C'\subseteq\mathcal B.$$
(3) For any $\mathcal C\in\mathbf F$ and any $x\in\mathbb N$ there exist $\mathcal C'$ and $A$, with $x\in A\in\mathcal C'\in\mathbf F$ and $\mathcal C'\preceq\mathcal C$, such that $$\mathcal C'\succeq\mathcal B\in\mathbf F\implies A\in\mathcal B.$$

Proof. Plainly (2)$\implies$(1) & (3); I will show that (1)$\implies$(2) and (3)$\implies$(2).

Proof of (1)$\implies$(2). Suppose $\mathcal C\in\mathbf F$. By (1) there exists $\mathcal C_0\in\mathbf F$ with $\mathcal C_0\preceq\mathcal C$ such that $\mathcal C_0$ is refinement-minimal. By the lemma there exists $\mathcal C'\in\mathbf F$ such that $\mathcal C'\preceq\mathcal C_0$ and $\mathcal C'$ is an antichain. Now, if $\mathcal C'\succeq\mathcal B\in\mathbf F$, then $\mathcal C'\preceq\mathcal B$; since $\mathcal C'$ is an antichain, it follows that $\mathcal C'\subseteq\mathcal B$.

Proof of (3)$\implies$(2). Let $\mathcal C_0=\mathcal C$. Using (3) we can construct $\mathcal C_n\in\mathbf F$ and $A_n\in\mathcal C_n$ for $n\in\mathbb N$ so that $\mathcal C_n\preceq\mathcal C_{n-1}$ and $n\in A_n$, and so that $\mathcal C_n\succeq\mathcal B\in\mathbf F\implies A_n\in\mathcal B$. It follows that $A_n\in\mathcal A_m$ for all $m\ge n$. Let $\mathcal C'=\{A_n:n\in\mathbb N\}$. Then $\mathcal C'\in\mathbf F$, and $\mathcal C'\preceq\mathcal C_n$ for all $n$, and $\mathcal C'\succeq\mathcal B\in\mathbf F\implies\mathcal C'\subseteq\mathcal B$.

Remark. I wanted to include the following statement but I couldn't prove that it's equivalent to the others:

(4) For any $\mathcal C\in\mathbf F$ and any $x\in\mathbb N$ there exist $\mathcal C'$ and $A$, with $x\in A\in\mathcal C'\in\mathbf F$ and $\mathcal C'\preceq\mathcal C$, such that $$\mathcal C'\succeq\mathcal B\in\mathbf F\implies\{A\}\preceq\mathcal B.$$