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

up vote 7 down vote accepted

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

  • So nice argument! Thank you for the help. – Taras Banakh Oct 11 at 19:58
  • You are welcome! – Nik Weaver Oct 11 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
    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. – YCor Oct 11 at 18:58
  • 2
    It's just a maximal subset of edges with containing no loop. – YCor Oct 11 at 19:07
  • 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). – Taras Banakh Oct 11 at 19:42
  • 1
    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. – YCor Oct 11 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.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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