Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $cn$ edges, can we bound the probability that it will be odd-$K_k$-minor-free, for interesting values of $c$ and $k$?

Motivation: DeMaine el al "simplifying graph decomposition" (Section 3 of paper, page 54 of slides) gives an algorithm to partition any odd-H-minor free graph into two parts such that deleting either part leaves a graph of bounded treewidth.

There's a negative result by Boedlander (paper, summary) showing that treewidth grows roughly as $\sqrt{n}$, so only tiny fraction of graphs are amenable to tree decomposition. It would be interesting to know how many more graphs are amenable to the "simplifying decomposition".

  • 1
    $\begingroup$ "Typical" is not well defined, so this question as currently stated will be hard to answer. To make the question more precise, you could, say, ask for for a threshold function t such that a random n-vertex m-edge graph is likely to be odd-H-minor free iff $m \ll t(n)$? $\endgroup$
    – Neal Young
    Commented Sep 2, 2021 at 18:36
  • 1
    $\begingroup$ added clarification $\endgroup$ Commented Sep 2, 2021 at 18:45


Your Answer

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