<p>Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of <a href="https://www.cs.princeton.edu/%7Ezdvir/apx11slides/erik-scribe.pdf" rel="nofollow noreferrer">notes</a>, page 20 of <a href="https://icerm.brown.edu/materials/Slides/sp-s14-rc3/Minors_and_Algorithms_%5D_Erik_Demaine,_Massachusetts_Institute_of_Technology.pdf" rel="nofollow noreferrer">slides</a>). For instance, for a random graph with <span class="math-container">$n$</span> vertices, <span class="math-container">$cn$</span> edges, can we bound the probability that it will be odd-<span class="math-container">$K_k$</span>-minor-free, for interesting values of <span class="math-container">$c$</span> and <span class="math-container">$k$</span>?</p>
<p>Motivation: DeMaine el al &quot;simplifying graph decomposition&quot; (Section 3 of <a href="https://epubs.siam.org/doi/abs/10.1137/1.9781611973075.28" rel="nofollow noreferrer">paper</a>, page 54 of <a href="https://icerm.brown.edu/materials/Slides/sp-s14-rc3/Minors_and_Algorithms_%5D_Erik_Demaine,_Massachusetts_Institute_of_Technology.pdf" rel="nofollow noreferrer">slides</a>) 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.</p>
<p>There's a negative result by Boedlander (<a href="https://pure.tue.nl/ws/portalfiles/portal/4394432/398349.pdf" rel="nofollow noreferrer">paper</a>, <a href="https://cstheory.stackexchange.com/questions/3657/typical-hardness-of-tree-decomposition/4177#4177">summary</a>) showing that treewidth grows roughly as <span class="math-container">$\sqrt{n}$</span>, 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 &quot;simplifying decomposition&quot;.</p>

CC BY-SA 4.0
2021-09-02T18:36:00.730Z
"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)$?
Neal Young
CC BY-SA 4.0
2021-09-02T18:45:53.990Z
added clarification
Yaroslav Bulatov
<ds.algorithms><graph-theory><graph-algorithms><treewidth>
How typical are odd-H-minor free graphs?
Yaroslav Bulatov
# How typical are odd-H-minor free graphs?

(Asked by: username_0 on 2021-09-02)

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](https://www.cs.princeton.edu/%7Ezdvir/apx11slides/erik-scribe.pdf), page 20 of [slides](https://icerm.brown.edu/materials/Slides/sp-s14-rc3/Minors_and_Algorithms_%5D_Erik_Demaine,_Massachusetts_Institute_of_Technology.pdf)). 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](https://epubs.siam.org/doi/abs/10.1137/1.9781611973075.28), page 54 of [slides](https://icerm.brown.edu/materials/Slides/sp-s14-rc3/Minors_and_Algorithms_%5D_Erik_Demaine,_Massachusetts_Institute_of_Technology.pdf)) 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](https://pure.tue.nl/ws/portalfiles/portal/4394432/398349.pdf), [summary](https://cstheory.stackexchange.com/questions/3657/typical-hardness-of-tree-decomposition/4177#4177)) 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".

**Tags:** ds.algorithms, graph-theory, graph-algorithms, treewidth
> **Comments:**
> **username_1**: "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)$?  
> **username_0**: added clarification  

---

## 0 answers

