Let $\mathcal U$ be a free ultrafilter on a set $X$. For $n\in\mathbb N$ let $\mathcal F$ be a family of $n$-element subsets of $X$ such that $\bigcup\mathcal F\in\mathcal U$.

Question. Is there a set $U\in\mathcal U$ and a subfamily $\mathcal E\subset\mathcal F$ such that $\bigcup\mathcal E\in\mathcal U$ and $|U\cap E|=1$ for every $E\in\mathcal E$?

I do not know the answer even for $n=2$ and countable set $X$.


Here's a try for $n=3$ which I think generalizes to any $n$.

Well-order $\mathcal{F}$ as $\{F_\alpha\}$. By discarding any $F_\alpha$ which is contained in $\bigcup_{\beta <\alpha} F_\beta$, we can ensure that each $F_\alpha$ contains at least one point which is not in any previous $F_\beta$, without affecting $U = \bigcup F_\alpha$.

We can now inductively construct a set $V \subset U$ with the property that $|V \cap F_\alpha|= 1$ or $2$ for all alpha. At each $\alpha$ at least one element of $F_\alpha$ is new and we can include it or not to ensure the condition for $F_\alpha$.

Now $U \setminus V$ has the same property, so since $U \in \mathcal{U}$, wlog we can assume $V \in \mathcal{U}$.

Let $\mathcal{E}_1 \subseteq \mathcal{F}$ consist of those $F_\alpha$ which intersect $V$ in exactly one point, and let $\mathcal{E}_2$ consist of the other $F_\alpha$, which all intersect $V$ in two points. If the union of $\mathcal{E}_1$ belongs to $\mathcal{U}$ then we are done. Otherwise the union of $\mathcal{E}_2$ belongs to $\mathcal{U}$ and this reduces us to the $n=2$ case.

The general reduction turns the problem for an arbitrary $n$ into the same problem for some smaller $n$.

  • $\begingroup$ So nice argument! Thank you for the help. $\endgroup$ – Taras Banakh Oct 11 '18 at 19:58
  • $\begingroup$ You are welcome! $\endgroup$ – Nik Weaver Oct 11 '18 at 20:09

For $n=2$ and any $X$: for each $x\in \cup \mathcal F$ fix any edge $(x,y)\in \mathcal F$ and draw an arrow from $x$ to $y$. Remove all other edges. Remaining edges still have the same union as $\mathcal{F}$, but they form a directed graph with outdegrees at most 1. Such a graph has a proper 3-coloring (it suffices to prove this for finite subgraphs by compactness theorem, and for them the result is well known and easy: remove the vertex with minimal in-degree, it is at most 1, and proceed by induction). One of three colors works.

  • 2
    $\begingroup$ You can alternatively take a covering forest of the graph (which constructs $\mathcal{E}$), and then you have a 2-coloring (fix 1 vertex of some color in each component, and elements of a single component have the same color iff they're at even distance), and then take the set of vertices of some fixed color. $\endgroup$ – YCor Oct 11 '18 at 18:58
  • 2
    $\begingroup$ It's just a maximal subset of edges with containing no loop. $\endgroup$ – YCor Oct 11 '18 at 19:07
  • $\begingroup$ Thank you for the answers. What about the case $n\ge 3$? (Starting from $n=3$ I have some applications to the problem of normality of hyperballeans). $\endgroup$ – Taras Banakh Oct 11 '18 at 19:42
  • 1
    $\begingroup$ My argument with covering forest does not work, I think. Instead, one consider a maximal non-covering subfamily of $\mathcal{E}$, so it has the same union: then the corresponding graph has the property that no edge joins two vertices of valency $\ge 2$. It follows that each of its component is a tree, with one vertex joined to all others. $\endgroup$ – YCor Oct 11 '18 at 19:55

Consider this with assuming that $\mathcal{F}$ consists of finite subsets of bounded cardinal; let $n$ be the max of these cardinals and let us argue by induction on $n$. The goal is to find $\mathcal{E}\subset\mathcal{F}$ and $U\in\mathcal{U}$ such that $U\subset\bigcup\mathcal{E}$ and and $|E\cap U|\le 1$ for every $E\in\mathcal{E}$.

First, consider a maximal subset $\mathcal{E}$ of the cover such that no element is in the union of others (we call this ``minimal"). So $V:=\bigcup\mathcal{F}=\bigcup\mathcal{E}$. Write $V=V_1\cup V_2$, where $V_2$ is the set of elements of $V$ that belong to at least two elements of $\mathcal{E}$. The minimality of $\mathcal{E}$ implies that no $E\in\mathcal{E}$ is contained in $V_2$ (i.e., has nonempty intersection with $V_1$).

Since the intersection of elements of $\mathcal{E}$ with $V_1$ are pairwise equal or disjoint, we can partition $V_1$ into $n$ subsets each intersecting, each element of $\mathcal{E}$ in at most a singleton. Hence we can conclude if $V_1\in\mathcal{U}$ (with $U$ being one of those $n$ subsets of $V_1$).

Otherwise, $V_2\in\mathcal{U}$. Since $|E\cap V_2|\le n-1$ for all $E\in\mathcal{E}$, we can conclude by induction (and find $U\subset V_2$).

PS Nik Weaver posted an answer while I was writing this one, but I still post, although I guess it's the same idea.

  • $\begingroup$ Thank you, Yves for the answer (in fact, MO is incredibly efficient). $\endgroup$ – Taras Banakh Oct 11 '18 at 22:44

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.