Given a hypergraph $H=(V,E)$ we associate to it its line graph $L(H)$ given by $V(L(H)) =E$ and $$E(L(H)) = \big\{\{e_1,e_2\}: e_1\neq e_2 \in E \text{ and } e_1\cap e_2 \neq \emptyset \big\}.$$

We say that a $H=(V,E)$ is a dense linear hypergraph if

  1. $V \notin E$,
  2. $\bigcup E = V$,
  3. whenever $e_1\neq e_2 \in E$ then $|e_1\cap e_2| \leq 1$, and
  4. given $a\neq b\in V$ there is $e\in E$ with $\{a,b\}\in e$.

Question. Given a simple, undirected graph $G$, is there a dense linear hypergraph $H$ such that $G$ is isomorphic to an induced subgraph of $L(H)$?


Choose an orientation of $G$. We will write $\vec{vw}\in E(G)$ for the edge with the orientation from $v$ to $w$. For every vertex $v\in V(G)$, define

$$\mathcal V(v):=\{v\}\;\cup\;\{(v,e)\mid e=\vec{wv}\in E(G)\}.$$

Let $H=(V,E)$ be the hypergraph with vertex set

$$V=\{v_0\}\;\cup\;\bigcup_{\llap{v\,\in\, }\rlap{V(G)}} \mathcal V(v).$$

In words: $H$ contains a distinguished vertex $v_0$, and for each vertex $v\in V(G)$, it contains a copy of $v$, as well as a further copy for every incoming edge to $v$. Now, for every $v\in V(G)$, let $H$ contain the edge

$$e_v:=\mathcal V(v)\;\cup\;\{(w,e)\mid e=\vec{vw}\in E(G)\}.$$

And also add an edge $\{v_0\}$. $H$ then satsifies conditions 1 - 3, and you can add additional edges to $H$ to make it satisfy 4 as well. The (induced) embedding of $G$ into $L(H)$ is obviously via $v\mapsto e_v$.

The distinguished vertex $v_0$ is there to make the construction satisfy condition 1 in the case thas $G$ consists of a single vertex. The extra $v$ in $\mathcal V(v)$ exists, so that vertices without incoming edges are correctly represented.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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