# How typical are odd-H-minor free graphs?

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

• "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)$? Sep 2, 2021 at 18:36
• added clarification Sep 2, 2021 at 18:45