<p>This is not an answer but is too long for a comment: </p>

<p>The graph you care about is called the <a href="https://en.wikipedia.org/wiki/Line_graph_of_a_hypergraph" rel="nofollow noreferrer">line graph of the hypergraph</a>. For usual graphs, it is well known that the line graph of an expander graph is also an expander graph (because vertex and edge expansion are equivalent). Whether this holds for hypergraphs probably depends on which of the many notions of expansion you can choose for hypergraphs/simplicial complexes. For one of these notions (based on the spectrum of an adjacency matrix of the hypergraph), this is mentioned as an open problem in the conclusion of <a href="https://www.theses.fr/2018NORMC207" rel="nofollow noreferrer">this thesis</a>.</p>

CC BY-SA 4.0
2018-10-19T11:09:48.643Z
2018-10-19T11:09:48.643Z
Arnaud
<p>I came up with this problem while thinking about an optimizing compiler.</p>

<p>Let <span class="math-container">$H$</span> be a hypergraph. From this we construct a graph <span class="math-container">$G_H$</span> as follows the vertices are the hyperedges of the hypergraph. There is an edge in <span class="math-container">$G_H$</span> whenever the hyperedges <span class="math-container">$e_1$</span> and <span class="math-container">$e_2$</span> have a vertex in <span class="math-container">$G$</span> in common.</p>

<p>I would like to know what I can say about the Cheeger constant of <span class="math-container">$G_H$</span>.</p>

<p>In fact I have a family <span class="math-container">$H_n$</span>, so this will go into whether there is a nonzero lower bound that works for all the <span class="math-container">$G_{H_n}$</span>.</p>

<expanders><hypergraphs>
Expander Graph from Hypergraph
AHusain
# Expander Graph from Hypergraph

(Asked by: username_0 on 2018-10-17)

I came up with this problem while thinking about an optimizing compiler.

Let $H$ be a hypergraph. From this we construct a graph $G\_H$ as follows the vertices are the hyperedges of the hypergraph. There is an edge in $G\_H$ whenever the hyperedges $e\_1$ and $e\_2$ have a vertex in $G$ in common.

I would like to know what I can say about the Cheeger constant of $G\_H$.

In fact I have a family $H\_n$, so this will go into whether there is a nonzero lower bound that works for all the $G\_{H\_n}$.

**Tags:** expanders, hypergraphs

---

## 1 answers

### Answer by username_1 on 2018-10-19. Score: 2 | Accepted answer

This is not an answer but is too long for a comment:

The graph you care about is called the [line graph of the hypergraph](https://en.wikipedia.org/wiki/Line_graph_of_a_hypergraph). For usual graphs, it is well known that the line graph of an expander graph is also an expander graph (because vertex and edge expansion are equivalent). Whether this holds for hypergraphs probably depends on which of the many notions of expansion you can choose for hypergraphs/simplicial complexes. For one of these notions (based on the spectrum of an adjacency matrix of the hypergraph), this is mentioned as an open problem in the conclusion of [this thesis](https://www.theses.fr/2018NORMC207).


---

