Let $H=(V,E)$ be a hypergraph. We call it $T_0$ if for all $x\neq y \in V$ there is $e\in E$ with $\{x,y\}\not\subseteq E$ and $\{x,y\}\cap e\neq \emptyset$ (i.e., $e$ contains exactly one of $x,y$).

If $H=(V,E)$ is a $T_0$-hypergraph, it is possible that $|E|<|V|$: Let $V=\mathbb{R}$ and let $E = \{(-\infty, q):q\in\mathbb{Q}\}$.

Question. Is there a $T_0$-hypergraph $H=(V,E)$ such that $2^{|E|} < |V|$?


There is a map $m: V \to \mathcal P(E)$, picking out the edges a vertex is contained in. Given $x \neq y \in V$, there is an edge $e$ containing precisely one of $x$ or $y$, and so $x$ and $y$ are not contained in precisely the same collection of edges. Therefore $m$ is injective and $|V| \leq |\mathcal P(E)| = 2^{|E|}$.

  • $\begingroup$ Very nice & concise, thanks for your argument! $\endgroup$ – Dominic van der Zypen Oct 10 '18 at 4: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.