# A property of an ultrafilter

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

• So nice argument! Thank you for the help. – Taras Banakh Oct 11 '18 at 19:58
• You are welcome! – 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.

• 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 '18 at 18:58
• It's just a maximal subset of edges with containing no loop. – YCor Oct 11 '18 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 '18 at 19:42
• 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 '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.

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