<p>Suppose we have a graph <span class="math-container">$G$</span> with treewidth <span class="math-container">$t$</span>. Let <span class="math-container">$p \in (0,1)$</span> be a constant. Then let's independently remove each edge from <span class="math-container">$G$</span> with probability <span class="math-container">$p$</span>. What is the expected treewidth of the resulting graph? I think it should be <span class="math-container">$\Omega(t)$</span>, but have little clue how to prove it.</p>
<p>For <span class="math-container">$n \times n$</span> grid there is another distribution such that each edge has constant probability to be removed and with probability 1 the treewidth of the resulting graph is at least <span class="math-container">$n/2$</span>. Let's pick the cells of the grid having odd coordinates <span class="math-container">$(2k+1,2\ell+1)$</span>. If we contract all these cycles we get a <span class="math-container">$(n/2)\times(n/2)$</span> grid with doubled edges. Then let our distribution remove exactly one of the edges from each of the squares and exactly one edge of each pair that becomes parallel if the cycles are contracted. The result always has <span class="math-container">$(n/2)\times(n/2)$</span> grid minor.</p>
<p>I am interested in such &quot;almost independent&quot; distribution on the sets of the removed edges that does not reduce treewidth too much as well.</p>

CC BY-SA 4.0
2021-10-20T12:17:16.117Z
Your belief is not correct. Take a graph $G=(V,E)$ with treewidth $t$ and replace each edge by a path of length $\Theta(\log n)$. Treewidth doesn't change. Now sampling with probability $p$ means that with high probability each "path" will be have at least one edge removed and the graph will be fall apart into stars which have treewidth $1$.
Chandra Chekuri
CC BY-SA 4.0
2021-10-20T13:32:21.607Z
Chandra, thanks a lot! I wonder whether the belief holds for $n \times n$ grid.. I will try to weaken the requirement for the distribution in a formal way :)
Artur Riazanov
CC BY-SA 4.0
2021-10-20T13:44:45.720Z
For grids people have studied worst-case removal of nodes/edges. You may find the following paper of David Eppstein useful. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p20
Chandra Chekuri
CC BY-SA 4.0
2021-10-20T13:53:11.030Z
Thank you! This seem to cover the case of $p=\Theta(1/n)$, not the constant $p$.
Artur Riazanov
<graph-theory><treewidth>
What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?
Artur Riazanov
# What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?

(Asked by: username_0 on 2021-10-20)

Suppose we have a graph $G$ with treewidth $t$. Let $p \in (0,1)$ be a constant. Then let's independently remove each edge from $G$ with probability $p$. What is the expected treewidth of the resulting graph? I think it should be $\Omega(t)$, but have little clue how to prove it.

For $n \times n$ grid there is another distribution such that each edge has constant probability to be removed and with probability 1 the treewidth of the resulting graph is at least $n/2$. Let's pick the cells of the grid having odd coordinates $(2k+1,2\ell+1)$. If we contract all these cycles we get a $(n/2)\times(n/2)$ grid with doubled edges. Then let our distribution remove exactly one of the edges from each of the squares and exactly one edge of each pair that becomes parallel if the cycles are contracted. The result always has $(n/2)\times(n/2)$ grid minor.

I am interested in such "almost independent" distribution on the sets of the removed edges that does not reduce treewidth too much as well.

**Tags:** graph-theory, treewidth
> **Comments:**
> **username_1**: Your belief is not correct. Take a graph $G=(V,E)$ with treewidth $t$ and replace each edge by a path of length $\Theta(\log n)$. Treewidth doesn't change. Now sampling with probability $p$ means that with high probability each "path" will be have at least one edge removed and the graph will be fall apart into stars which have treewidth $1$.  
> **username_0**: Chandra, thanks a lot! I wonder whether the belief holds for $n \times n$ grid.. I will try to weaken the requirement for the distribution in a formal way :)  
> **username_1**: For grids people have studied worst-case removal of nodes/edges. You may find the following paper of David Eppstein useful. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p20  
> **username_0**: Thank you! This seem to cover the case of $p=\Theta(1/n)$, not the constant $p$.  

---

## 0 answers

