1
$\begingroup$

Let $H=(V,E)$ be a hypergraph. For $v\in V$ we let $v^* = \{e\in E:v\in e\}$. We define the dual of $H$ by $H^*= (E, V^*)$ where $V^* = \{v^*: v\in V\}$. We say that a $H$ is self-dual if $H \cong H^*$.

Is there a self-dual hypergraph $H = (\omega, E)$ with the following property?

Whenever $e_0\neq e_1 \in E$ we have both $e_0 \not\subseteq e_1$ and $|e_0| \neq |e_1|$.

$\endgroup$
2
  • $\begingroup$ A thought: if I'm thinking correctly then this is equivalent to the existence of a symmetric $\omega\times\omega$ matrix with the same property. If so, this gives a simple construction: let $e_1=\{v_1, v_2\}$; this then implies that $v_1\in e_2$. Let $e_2$ be a 3-vertex edge such that $v_2\not\in e_2$; in particular, the first such lexicographically, $e_2 = \{v_1, v_3, v_4\}$. This then gives additional constraints on $e_3$ and $e_4$ saying that $v_2$ is a member of both; choose the first $e_3$ with 4 edges such that $v_2\in e_3$ and $e_2\not\subset e_3$, etc... $\endgroup$ Commented Sep 7, 2021 at 20:44
  • $\begingroup$ Each $e_n$ will have exactly one $v_i$ with $i\leq n$, and $n$ vertices $v_i$ with $i\gt n$. We can even take the latter as being $v_{f(n-1)+2}\ldots v_{f(n)+1}$, where $f(i)$ is the sum-of-integers function $f(i)=\frac12 i(i+1)$. $\endgroup$ Commented Sep 7, 2021 at 20:50

1 Answer 1

2
$\begingroup$

Expanding my comments into an answer: by rephrasing this as a question of constructing a symmetric $\omega\times\omega$ matrix with the same properties, we can give an explicit construction. For convenience's sake I'm going to start numbering at 0. Let $e_0 = \{v_0, v_1\}$ and for $n\geq 1$ let $e_n = \{v_i\} \cup \{v_j: f(n)\lt j\leq f(n+1)\}$, where $f(n)$ is the sum-of-integers function $f(n) = \frac12n(n+1)$ and $i$ is the unique number such that $f(i)\lt n\leq f(i+1)$ — in other words, $i$ is chosen to make the generated matrix symmetric.

This hypergraph has the nice property of being connected: for any two vertices there's some chain of edges that connects them to each other. In fact, it's a tree; for any two vertices there's exactly one chain of edges connecting them, or from a different perspective for any edge $e_i$ there's exactly one edge $e_j$ with $j\lt i$ and $e_i\cap e_j\neq\emptyset$. By allowing for more overlap in one half of the matrix, we can get 'greater' connectivity: for instance, take $e_0=\{v_0, v_1, v_2\}$, $e_1 = \{v_0, v_2, v_3, v_4\}$, $e_2 = \{v_0, v_1, v_4, v_5, v_6, v_7\}$, etc.

$\endgroup$
1
  • 1
    $\begingroup$ Beautiful - thank you very much, Steven! $\endgroup$ Commented Sep 8, 2021 at 9:50

You must log in to answer this question.

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