Tangled Paths: A Random Graph Model from Mallows Permutations

Abstract

We introduce the random graph $\mathcal{P}(n,q)$ which results from taking the union of two paths of length $n\ge 1$, where the vertices of one of the paths have been relabelled according to a Mallows permutation with parameter $0<q(n)\le 1$. This random graph model, the tangled path, goes through an evolution: if $q$ is close to $0$ the graph bears resemblance to a path, and as $q$ tends to $1$ it becomes an expander. In an effort to understand the evolution of $\mathcal{P}(n,q)$ we determine the treewidth and cutwidth of $\mathcal{P}(n,q)$ up to log factors for all $q$. We also show that the property of having a separator of size one has a sharp threshold. In addition, we prove bounds on the diameter, and vertex isoperimetric number for specific values of $q$.

36 pages, 7 figures. Strengthened Theorems 1.1 & 1.4