6
$\begingroup$

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$ ?
$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This stage construction is beautiful - thanks! $\endgroup$ – Dominic van der Zypen Aug 16 '17 at 6:36
  • $\begingroup$ 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.) $\endgroup$ – Péter Komjáth Aug 17 '17 at 6:27
  • $\begingroup$ @PéterKomjáth: I don't see it either! I will edit soon to limit what is being claimed. $\endgroup$ – Keith Kearnes Aug 18 '17 at 16:34
  • $\begingroup$ Is it possible to construct a counterexample to $X'\subseteq \bigcup {\cal U}'$ for a limit number of steps? $\endgroup$ – Dominic van der Zypen Oct 23 '17 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.