Tangled paths: a random graph model from Mallows permutations (Q6977157)

This paper introduces the random graph \(\mathcal{P}(n, q)\) which results from taking the union of two paths of length \(n>1\), where the vertices of one of the paths have been relabelled according to a Mallows permutation. The Mallows distribution has a parameter \(q\) which controls the amount of `tangled-ness' of the graph. The authors restrict to \(q \in [0, 1]\) as up to a relabelling, reversing the permutation does not affect the construction. This random graph model, the tangled path, goes through an evolution. When \(q \rightarrow 0\), the \((n, q)\)-Mallows measure converges weakly to the degenerate distribution on the identity permutation. On the other hand, if \(q=1\), then the Mallows measure is the uniform measure on \(S_n\). By the above observation, \(\mathcal{P}(n, 0)\) is a path and \(\mathcal{P}(n, 1)\) is an expander with high probability. The present work takes the first steps in understanding the structure of \(\mathcal{P}(n, q)\) for intermediate values of \(q\), unlocking the rich structure of graphs generated from two simple layers which are both influenced to some extent by a shared underlying `geography'. Informally, if \(q\) is not tending to \(1\) too fast, then \(\mathcal{P}(n, q)\) is `path-like'. For \(q \rightarrow 1\) sufficiently fast, the complexity of the structure grows smoothly with \(q\) in the sense of treewidth. The treewidth is a natural parameter as many NP-hard problems become tractable when parametrised by the treewidth. To prove a lower bound on the treewidth, the authors use consecutive patterns in the Mallows permutations to find smaller tangled paths with a higher \(q\) parameter as minors in the tangled path. To prove corresponding upper bounds the authors control the cutwidth by bounding the number of `long' edges created during the \(q\)-Mallows process. The authors also show that the property of having a separator of size one has a sharp threshold and give a linear bound on the diameter.