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?

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

Your Answer

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

Browse other questions tagged or ask your own question.