# Small dense subsets in “Hausdorff” hypergraphs

Let $H=(V,E)$ be a hypergraph. We call it Hausdorff if for all $x\neq y \in V$ there are $e_1,e_2\in E$ with $e_1\cap e_2 = \emptyset$ such that $x\in e_1$ and $y\in e_2$. We say that $D\subseteq V$ is dense if $D\cap e \neq \emptyset$ for all $e\in E\setminus\{\emptyset\}$.

If $V$ is an infinite set, $H=(V,E)$ is Hausdorff, and $D\subseteq V$ is dense, is it possible that $2^{|D|} < |E|$?

• Yes. Let V be a square array and D its diagonal, say D has 5 members. You need ten sets to ensure Hausdorff, and you have about 2^20 subsets left to play with to which you add a member of D. Likely you can optimize this to have D much smaller than the logarithm of E. Gerhard " Think Of Symmetric Block Designs" Paseman, 2017.09.20. – Gerhard Paseman Sep 20 '17 at 14:12
• In fact, by a combinatiorial compactification process, you can turn any sufficiently Hausdorff space into one where D is a dense set of size two. For any pair of distinct points x and y from X, if there are sets R and S separating them, and similarly subsets T and V, add R union a and V union a and S union b and T union b to your hypergraph on X union a union b. After all pairs of points are handled, "color" the rest of the open sets arbitrarily. Gerhard "'Combinatorial Compactification': I Like It!" Paseman, 2017.09.20. – Gerhard Paseman Sep 20 '17 at 14:25
• Or more simply, have V be arranged in a rectangular fashion, with E including the rows and the columns. For each set S which is a row or column, add S union a and S union b to the hyper graph on V union a union b. For all other edges T in E on V, add T union a and/or T union b as it suits you. Then the doubleton set of a and b is dense in V union a union b. Gerhard "Leaves Greater Generality To You" Paseman, 2017.09.20. – Gerhard Paseman Sep 20 '17 at 14:53
• Note that I want $V$ to be infinite... not sure if I understand your comments completely. – Dominic van der Zypen Sep 20 '17 at 14:56
• OK. I will post the greater generality. Gerhard "As Opposed To Greater Admiralty" Paseman, 2017.09.20. – Gerhard Paseman Sep 20 '17 at 15:39

Take $V$ to be the set of ultrafilters on $\omega$ and let $E \subset P(V)$ be the smallest subset closed under arbitrary unions containing all sets of the form $[X]= \{ p \in V: X \in p \}\subset V$ where $X \subset \omega$ is infinite and co-infinite.

Fact: The hyper-graph $(V,E)$ is Hausdorff.

Proof: Let $p, q \in V$ be distinct, then there is some $X \in p$ with $\,\omega \backslash X \in q$. As such, $p \in [X]\in E$, $q \in [\omega \backslash X]\in E$ and $[X] \cap [\omega \backslash X] = \emptyset$.)

Fact: The set $D = \{ p \in V: (\exists s \subset \omega)(|s| < \omega \wedge s \in p)\}$ of principal ultrafilters on $\omega$ is countable and dense with respect to $(V,E)$.

Proof: For any $\mathcal E \in E$, there is some infinite and co-infinite $X \subset \omega$ with $[X] \subset \cal E$; since $X$ is non-empty we can find some $n\in X$, in which case $p = \{ Y \subset \omega: n \in Y\} \in D\cap \cal E$.)

Fact: Assuming $\sf AC$: $2^{|D|}=\mathfrak{c} < 2^{\mathfrak{c}} \leq \vert E \vert$.

Proof: Let $\mathcal{A} = \{ A_\alpha: \alpha \in \mathfrak{c}\}\subset P(\omega)$ be an almost disjoint family of infinite subsets of $\omega$ of size $\mathfrak{c}$ and for any non-empty $I \subset \mathfrak{c}$ define $\mathcal{E}(I) = \bigcup \{ [A_\gamma]: \gamma \in I \}$ . It follows that,

$$I \neq J \implies \mathcal{E}(I) \neq \mathcal{E}(J)$$

since, without loss of generality, we can assume there is some $\gamma \in I \backslash J$, in which case any non-principal ultrafilter containing $A_\gamma$ will witness $\mathcal{E}(I) \backslash \mathcal{E}(J) \neq\emptyset$ (that such an ultrafilter exists is a consequence of $\sf AC$.) Nothing that $E$ is closed under unions, we have $\mathcal{E}(I) \in E$ and it follows that $2^{\vert D \vert} = \mathfrak{c} < \vert P(\mathfrak{c}) \vert \leq \vert E \vert$.

• Why do you need E closed under union (or finite intersection)? I am not seeing yet where the argument needs it. Gerhard "Remember, It's Hypergraphs, Not Topologies" Paseman, 2017.09.20. – Gerhard Paseman Sep 21 '17 at 0:20
• @GerhardPaseman The third fact requires closure under $\leq\mathfrak{c}$-unions which in this case is the same as arbitrary unions; but you're right I don't need finite-intersections. I'll change it to make it more clear. – Not Mike Sep 21 '17 at 0:25

Let H be any Hausdorff Hypergraph. We build G, a Greater (hyper-)Graph which has a dense set of two points and is also Hausdorff. When H has enough edges, G will satisfy the inequality of having more than $2^2$ edges.

The ground set for G has only two points more than the ground set for H. I call these points b and c. For every nonempty edge e from H, add edges e union (singleton) b and e union (singleton) c to G. As H is Hausdorff (and assume H has more than one point for its ground set, otherwise add singletons b and c to G also), G is Hausdorff also. Further, {b,c} is dense in G. For examples satisfying your inequality, make sure H has more than two nonempty edges.

Gerhard "Greater Generality Gives Greater Good" Paseman, 2017.09.20.

• Note that for any H which has two or fewer points and is Hausdorff, H already has a dense subset of size at most two. So for every cardinality of ground set for G, there is an edge set for G which is Hausdorff and has a two (or fewer) element dense subset. Very few of these G have 4 or fewer edges. Gerhard "What More Could One Want?" Paseman, 2017.09.20. – Gerhard Paseman Sep 20 '17 at 16:35
• So a simple version of this is $V=\{a,b\}\cup S$ and $E=\{\{a,x\}:x\in S\}\cup\{\{b,x\}:x\in S\}$. If $x\neq y$ are in $S$, then $\{a,x\}$ and $\{b,y\}$ separate them and $\{a,b\}$ is dense. – Péter Komjáth Sep 22 '17 at 5:13
• @Peter, yes, if you just need "few" edges, then you can make a minimal base that way. Gerhard "Maybe Ikea Sells Minimal Hypergraphs?" Paseman, 2017.09.22. – Gerhard Paseman Sep 22 '17 at 14:03