3
$\begingroup$

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

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Very nice & concise, thanks for your argument! $\endgroup$ Commented Oct 10, 2018 at 4:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .