# Refinement-minimal intersecting covers

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?

• I would try to approach this with Zorns lemma. I would like to consider the set of intersecting covers of $X$ as a poset, but as you stated, refining is not antisymmetric. Thus we can pass to equivalence classes of intersecting covers where $C\sim D$ iff $C\le D$ and $D\le C$. Then I would think about the assumption on chains in Zorns lemma. Commented Apr 17 at 8:18
• Is there an obvious answer in the special case where $X=\omega$ and $\mathcal C$ is an intersecting cover whose elements are finite sets? In this case I don't think Zorn's lemma or the axiom of choice would come up. But maybe this case is trivial and I'm just not clever enough to see it.
– bof
Commented Apr 18 at 3:14
• As an example of an intersecting cover of $\omega$ by finite sets which has no linear refinement, let $\mathcal C$ consist of the sets $\{0,2,4\}$, $\{1,3,4\}$, and $\{0,1,n\}$ where $n\ge5$. Note that $\mathcal C$ is a refinement-minimal cover and is not linear.
– bof
Commented Apr 19 at 0:53
• If $\mathcal C$ is an intersecting cover of $X$ which is linear and has the property that, for each $A\in\mathcal C$, there is a unique element $a\in A$ which is covered by no other element of $\mathcal C$, then $\mathcal C$ is a minimal cover. Is that what you meant?
– bof
Commented Apr 19 at 2:58
• Ah, yes, thanks @bof, that's what I meant, but I wrote it in a wrong way. Commented Apr 19 at 7:44

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?

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.

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

• Thanks a lot @bof for this effort! I find statement (4) particularly intriguing. (Obviously one should extend the definition of $\preceq$ to all non-empty subsets of ${\cal P}(X)$, not just covers, because $\{A\}$ intersecting, but usually not a cover.) Also, I will have to think which of the implications between (1),(2),(3) hold in the general setting, not just ${\bf F}$. (Of course some implications are trivial.) Commented Apr 23 at 7:00