2
$\begingroup$

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

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

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\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$ Sep 21, 2017 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, 2017 at 0:25
2
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Sep 20, 2017 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$ Sep 22, 2017 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$ Sep 22, 2017 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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