Is there a theory of hypergraph minors? I could only find some attempts to define them at papers/theses, whose main topic was something else. What would be a useful definition? Does the hypergraph version of the Robertson–Seymour theorem hold?

  • $\begingroup$ Arguably one of the baby steps of graph minor theory is the Wagner theorem on planar graphs. Already this is highly non-trivial for hypergraphs. Recent work of Carmesin has provided a finite list of forbidden minors (for some definition of minor) for the embeddability of simply-connected locally 3-connected 2-complexes in R^3, but there are infinite antichains when these hypotheses are lifted. Related notions of minor towards embedabillity have also been introduced by Nevo and Wagner $\endgroup$ – Arnaud Mar 8 at 14:47

I think both questions of the OP are answered in: Hypertree-depth and minors in hypergraphs (2012)

Let $H$ and $H′$ be hypergraphs. Then $H$ is a minor of $H′$ if $H$ can be obtained from $H′$ by a sequence of operations of the following kinds:
• vertex deletion,
• contraction of (the edge between) two vertices that are contained in a common hyperedge,
• addition of ahyperedge $e$ such that the set $e$ induces a clique in the underlying graph, and
• deletion of a proper subhyperedge.

For graphs, a famous result by Robertson and Seymour shows that testing for a fixed minor is solvable in cubic time. In contrast, testing for a fixed hypergraph minor can be NP-hard (section 6.4).

  • $\begingroup$ I don't think this is the Robertson-Seymour theorem OP is refering to. My guess would go towards this theorem. $\endgroup$ – Wojowu Mar 7 at 12:57
  • 1
    $\begingroup$ Yes, I've seen this paper and in fact they even provide an infinite antichain (giving a counter-example to the generalization of the Robertson-Seymour theorem). So is this paper on cops and robbers really the best (and only?) reference for hypergraph minors? More importantly, is there no other natural definition? $\endgroup$ – domotorp Mar 7 at 13:20

Your Answer

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

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