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

  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Sep 20 '17 at 14:12
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Sep 20 '17 at 14:25
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Sep 20 '17 at 14:53
  • $\begingroup$ Note that I want $V$ to be infinite... not sure if I understand your comments completely. $\endgroup$ – Dominic van der Zypen Sep 20 '17 at 14:56
  • $\begingroup$ OK. I will post the greater generality. Gerhard "As Opposed To Greater Admiralty" Paseman, 2017.09.20. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Sep 21 '17 at 0:20
  • $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Sep 20 '17 at 16:35
  • $\begingroup$ 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. $\endgroup$ – Péter Komjáth Sep 22 '17 at 5:13
  • $\begingroup$ @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. $\endgroup$ – Gerhard Paseman Sep 22 '17 at 14:03

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.