1
$\begingroup$

Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.

We say hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic, in symbols $H_1\cong H_2$, if there is a bijection $\varphi:V_1\to V_2$ such that $\varphi(e_1)\in E_2$ whenever $e_1\in E_1$, and $\varphi^{-1}(e_2)\in E_1$ whenever $e_2 \in E_2$.

Let $[\omega]^\omega$ denote the set of infinite subsets of $\omega$, and let $E_1, E_2\subseteq [\omega]^\omega$ such that $\bigcup E_i = \omega$ for $i=1,2$. Let $H_i = (\omega, E_i)$ for $i=1,2$.

Question. If $H_1^* \cong H_2^*$, do we necessarily have $H_1\cong H_2$?

$\endgroup$
3
  • 1
    $\begingroup$ I can't parse your title. Can you clarify it? $\endgroup$
    – David Roberts
    Commented Jun 28 at 7:06
  • 1
    $\begingroup$ I think the isomorphism definition needs some work. If $\varphi$ is from $V_1$ then $\varphi(e_1)$ does not automatically make sense for $e_1 \in E_1$. $\endgroup$ Commented Jun 28 at 7:47
  • $\begingroup$ I have tried to make the title catchier. - @JukkaKohonen : $\varphi(e_1)= \text{im}(\varphi|_{e_1})$, so $\varphi(e_1)$ is the image of $e_1\subseteq V_1$ under $\varphi$. This is a subset of $V_2$. Now $E_2$ is a collection of subsets of $V_2$. Whence the requirement $\varphi(e_1)\in E_2$. Does that make sense? $\endgroup$ Commented Jun 28 at 11:30

1 Answer 1

3
$\begingroup$

Counterexample. Let $E_1=\{e_0,e_1\}$ and $E_2=\{e_0,e_2\}$ where $$e_0=\{0,1\}\cup\{2,4,6,8,\dots\},$$ $$e_1=\{0\}\cup\{3,5,7,9,\dots\},$$ $$e_2=\{0,1\}\cup\{3,5,7,9,\dots\}.$$ Then $(\omega,E_1)\not\cong(\omega,E_2)$, but $(E_1,V_1^*)\cong(E_2,V_2^*)$ since $V_1^*=\{\{e_0\},\{e_1\},\{e_0,e_1\}\}$ and $V_2^*=\{\{e_0\},\{e_2\},\{e_0,e_2\}\}.$

On the other hand, if $H=(V,E)$ is a hypergraph with the property that $E_v\ne E_w$ whenever $v\ne w$, then the dual hypergraph $H^*$ has the same property, and $(H^*)^*\cong H$. Hence, if $H_1$ and $H_2$ are two such hypergraphs, then $H_1^*\cong H_2^*\implies H_1\cong H_2$.

$\endgroup$

You must log in to answer this question.

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