# Kleinberg Rubinfeld Short Paths in Expander Graphs for Hypergraphs

In the 1996 paper "Short Paths in Expander Graphs" by Kleinberg and Rubinfeld, the authors show a randomized polynomial-time algorithm for finding an embedding of a graph $H$ into a graph $G$, if $G$ is a regular expander on $n$ nodes and $H$ is a graph on at most $cn / \log^k n$ nodes and edges, where $c$ and $k$ are constants.

I have searched for a while for an extension of this result to hypergraphs, with no luck. I was wondering if anyone was aware of a similar result for hypergraphs?

• what is your definition of hypergraph expander? – Igor Shinkar Apr 6 '16 at 18:28