# Induced subgraphs of the line graph of a dense linear hypergraph

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.