# Minimal subcoverings of a cover whose sets intersect in at most $1$ point

Suppose we are given a nonempty set $X$. Let ${\cal U}$ be a set of subsets of $X$ such that

1. $\bigcup {\cal U} = X$, and
2. $U_1\neq U_2\in {\cal U}$ implies $|U_1\cap U_2| \leq 1$.

Is there a subcollection ${\cal U}_0\subseteq {\cal U}$ such that

1. $\bigcup {\cal U}_0 = X$, and
2. if $U\in{\cal U}_0$ then $\bigcup \big({\cal U}_0 \setminus \{U\}\big) \ne X$ ?

Edit 08/21/2017

Péter Komjáth detected a gap in my original argument, so I will edit it now to limit what is claimed.

I claim that if (i) $|X|=\omega$, or if (ii) $|X|=\kappa>\omega$ and $\mathcal U$ is a locally finite cover of $X$, then the question has an affirmative answer. Here I say that $\mathcal U$ is a locally finite cover of $X$ if each element of $X$ is contained in only finitely many elements of $\mathcal U$.

From this point until the last paragraph, the only edits I intend to make involve replacing some $U$'s with ${\mathcal U}$'s. (These were typos in my original writeup.)

I will explain how to construct ${\mathcal U}_0$. Let $(x_{\lambda})_{\lambda<\kappa}$ be an enumeration of $X$. I will examine the elements of $X$, roughly in order, and decide which elements of ${\mathcal U}$ to put into ${\mathcal U}_0$.

To keep track of things, I will write $(X,\emptyset)$ and $({\mathcal U},\emptyset)$ to indicate the starting state and $(\emptyset,X)$ and $(\emptyset, {\mathcal U}_0)$ to indicate the ending state. Middle states will be of the form $(X',X'')$ and $({\mathcal U}', {\mathcal U}'')$ where $\{X',X''\}$ is a partition of $X$ into two cells, where the elements of $X''$ have been `handled' and the elements of $X'$ have yet to be handled. As we handle the elements of $X$ we move them from $X'$ to $X''$ and either discard sets from ${\mathcal U}'$ or else we move some sets from ${\mathcal U}'$ to ${\mathcal U}''$. Throughout the process we will arrange that $X'$ is contained in the union of the sets in ${\mathcal U}'$, while ${\mathcal U}''$ is a minimal cover of $X''$. The process will end with a minimal cover ${\mathcal U}_0$ of $X$.

As I move through the process I will want to maintain an additional assumption. As mentioned above, I will assume at each stage $(X',X'')$ and $({\mathcal U}', {\mathcal U}'')$ that $X'$ is contained in the union of the sets in ${\mathcal U}'$, and ${\mathcal U}''$ is a minimal cover of $X''$. (This includes the assumption that $\bigcup_{u\in {\mathcal U}''}u=X''$.) For each $v\in {\mathcal U}''$ the set ${\mathcal U}''-\{v\}$ does not cover $X''$, so there is an element $x_v\in X''$ contained in $v$ and in no other element of ${\mathcal U}''$. Call $x_v$ an anchor for $v$. The assumption that ${\mathcal U}''$ is a minimal cover of $X''$ means exactly that every $v\in {\mathcal U}''$ has an anchor in $X''$. The additional assumption I intend to maintain throughout the process is: no set in ${\mathcal U}'$ contains an anchor $x_v\in X''$ of an element $v\in {\mathcal U}''$.

The additional assumption holds in the starting state, since ${\mathcal U}''=\emptyset$ at the beginning.

The construction really starts now. I allow two ways for the process to move forward.

A move of type 1.

We are at stage $(X',X'')$ and $({\mathcal U}', {\mathcal U}'')$, where (i) $X'$ is contained in the union of the sets in ${\mathcal U}'$, (ii) ${\mathcal U}''$ is a minimal cover of $X''$, and (iii) no set in ${\mathcal U}'$ contains an anchor $x_v\in X''$ of an element $v\in {\mathcal U}''$.

I define a directed graph with vertex set $X'$. Write $x\to y$ if the implication [$x\in u$ implies $y\in u$] holds for every $u\in {\mathcal U}'$. There will be loops on every $x\in X'$, but they are unimportant. If $x\to y$ is a nonloop, then any $u\in {\mathcal U}'$ that contains $x$ must also contain $y$. Therefore there cannot be two sets $u, v\in {\mathcal U}'$ containing $x$, since this would yield $u\cap v \supseteq \{x,y\}$, contradicting $|u\cap v|\leq 1$. Thus each $x\in X'$ that is the tail vertex of a nonloop is contained in a unique $u_x\in {\mathcal U}'$. I intend to (i) move all tail vertices $x$ of nonloops from $X'$ to $X''$, move all associated sets $u_x$ from ${\mathcal U}'$ to ${\mathcal U}''$, (iii) treat $x$ as the anchor of $u_x$, and (iv) move from $X'$ to $X''$ all other elements covered by the $u_x$'s.

I claim that after these steps we again have a stage $(\overline{X}',\overline{X}'')$ and $(\overline{\mathcal U}', \overline{\mathcal U}'')$, where the assumptions are satisfied. (I overlined sets $X', X'', {\mathcal U}', {\mathcal U}''$ to indicate the state of the set after the step is completed.) To see that $\overline{X}'\subseteq \bigcup_{u\in \overline{\mathcal U}'} u$ it suffices to note that $\overline{X}'\cup \overline{X}''=X= {X}'\cup {X}''$, $\overline{\mathcal U}'\cup \overline{\mathcal U}''= {\mathcal U}'\cup {\mathcal U}''$ (which covers $X$), and $\overline{X}''=\bigcup_{u\in \overline{\mathcal U}''} u$. To see that $\overline{\mathcal U}''$ is a minimal cover of $\overline{X}''$ it suffices to note that $\overline{X}''=\bigcup_{u\in \overline{\mathcal U}''} u$ and each $u\in \overline{\mathcal U}''$ has an anchor in $\overline{X}''$. Finally, no set in $\overline{\mathcal U}'$ contains an anchor element in $\overline{\mathcal U}''$ since (i) $\overline{\mathcal U}'\subseteq {\mathcal U}'$, so no set in $\overline{\mathcal U}'$ contains an old anchor element (one that existed in $X''$), and (ii) no set in $\overline{\mathcal U}'$ contains one of the new anchors $x$, since each such $x$ was a tail of a nonloop.

The preceding step accomplishes something useful only if the associated graph is not discrete. If it is, then we need

A move of type 2.

Suppose now we are at a stage $(X',X'')$ and $({\mathcal U}', {\mathcal U}'')$ where the associated directed graph is discrete. If we are not yet to the stage where $X'=\emptyset$, then choose the element $x\in X'$ that has least index in our earlier enumeration $(x_{\lambda})_{\lambda<\kappa}$, and add it to $X''$. I would like it to be an anchor element, so choose any $u\in {\mathcal U}'$ that contains $x$ and add $u$ to ${\mathcal U}''$. Also, add all elements of $u$ to $X''$. To ensure that $x$ remains an anchor element for the rest of the construction, delete all $v\in {\mathcal U}'$ containing $x$. Now the move is complete.

I claim that after these steps we again have a stage $(\overline{X}',\overline{X}'')$ and $(\overline{\mathcal U}', \overline{\mathcal U}'')$, where the assumptions are satisfied. To see that $\overline{X}'\subseteq \bigcup_{u\in \overline{\mathcal U}'} u$ and also that $\overline{\mathcal U}'$ contains no anchor elements in $X''$, it suffices to observe that, since at the start of the step the associated graph was discrete, if $y\in \overline{X}'\subseteq X'$, then there is a $v\in {\mathcal U}'$ such that $y\in v$ and $x\notin v$. The set $v$ contains none of the old anchor elements, by induction, and $v$ does not contain the new anchor element $x$, so $v\in\overline{\mathcal U}'$ and $v$ contains no anchors from $\overline{X}''$. To see that $\overline{\mathcal U}''={\mathcal U}''\cup\{u\}$ is a minimal cover of $\overline{X}''=X''\cup u$ it is enough to note that every set in $\overline{\mathcal U}''$ has an anchor in $\overline{X}''$.

If we alternate between moves of these two types we will eventually exhaust $X$, because moves of type 1 cannot occur twice in a row and moves of type 2 progress through the enumeration of $X$. We will end with $(\emptyset,X)$ and $(\emptyset, {\mathcal U}_0)$ where ${\mathcal U}_0$ is a minimal cover of $X$.

Last paragraph

As Péter Komjáth pointed out, the inclusion $X'\subseteq \bigcup {\mathcal U}'$ might not be preserved at nonzero limit stages for general $X$, $\mathcal U$. This is not a problem if $|X|=\omega$, since there are no nonzero limit stages. I claim that it is also not a problem if $|X|=\kappa>\omega$ and $\mathcal U$ is a locally finite cover of $X$. Without offering the full details, the reason is that: (i) the inclusion $X'\subseteq \bigcup {\mathcal U}'$ is preserved at successor stages, and (ii) when $\mathcal U$ is a locally finite covering, a point of $X'$ can only be uncovered at a successor stage if our operations only allow moving sets from ${\mathcal U}'$ to ${\mathcal U}''$ or deleting sets from ${\mathcal U}'$.

• This stage construction is beautiful - thanks! – Dominic van der Zypen Aug 16 '17 at 6:36
• I don't see why the condition $X'\subseteq \bigcup {\cal U}'$ holds after a limit number of steps. (Apologies if this is a triviality.) – Péter Komjáth Aug 17 '17 at 6:27
• @PéterKomjáth: I don't see it either! I will edit soon to limit what is being claimed. – Keith Kearnes Aug 18 '17 at 16:34
• Is it possible to construct a counterexample to $X'\subseteq \bigcup {\cal U}'$ for a limit number of steps? – Dominic van der Zypen Oct 23 '17 at 6:52