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}$.


1 Answer 1


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. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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