7
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\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
    Commented Mar 8, 2019 at 14:47

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't think this is the Robertson-Seymour theorem OP is refering to. My guess would go towards this theorem. $\endgroup$
    – Wojowu
    Commented Mar 7, 2019 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
    Commented Mar 7, 2019 at 13:20
  • $\begingroup$ I think this sequence of some operations you are describing only works in the finite case - but in the infinite case, I think my answer below might work? $\endgroup$
    – Dominic van der Zypen
    Commented Sep 18, 2019 at 8:23
0
$\begingroup$

In a note concerning a version of Hadwiger's conjecture for hypergraphs, I once defined what a (complete) minor map of a hypergraph is, and probably this can be used to define a notion of "minor of hypergraph". (If you are interested in the note, which I did not publish or put on arXiv, I am happy to send it to you.)

For the following definitions assume that $H=(V,E)$ is a hypergraph.

A subset $\emptyset \neq S \subseteq V$ is said to be connected if for all $S_1 \subseteq S$ with $\emptyset \neq S_1 \neq S$ there are $x\in S_1, y\in S\setminus S_1$ and $a \in E$ such that $x,y \in a$.

Let $S,T \neq \emptyset$ be disjoint subsets of $V$. They are said to be connected to each other if there are $s \in S, t\in T$ and $a\in E$ such that $x,y \in a$.

A map $m: \kappa \to {\cal P}(V)\setminus \{\emptyset\}$ is said to be a complete minor map if

  1. $m(x)$ is connected for all $x\in \kappa$;
  2. for $x\neq y \in \kappa$ we have $m(x)\cap m(y) = \emptyset$ and $m(x),m(y)$ are connected to each other.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .