2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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
    Sep 2, 2021 at 18:36
  • 1
    $\begingroup$ added clarification $\endgroup$
    – Yaroslav Bulatov
    Sep 2, 2021 at 18:45

0

Reset to default

Your Answer

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