Tangled paths: a random graph model from Mallows permutations
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.
- A note on the width of sparse random graphs
- A Separator Theorem for Planar Graphs
- Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Cliques in the union of \(C_4\)-free graphs
- Cliques in the union of graphs
- Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions
- Decompositions into isomorphic rainbow spanning trees
- Decompositions into spanning rainbow structures
- Degree sequence of random permutation graphs
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Every monotone graph property has a sharp threshold
- Expander graphs and their applications
- Expanders via Random Spanning Trees
- How many graphs are unions of k‐cliques?
- How many random edges make a dense graph hamiltonian?
- scientific article; zbMATH DE number 3728625 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 4121424 (Why is no real title available?)
- Independent sets in the union of two Hamiltonian cycles
- Introduction to Random Graphs
- Lengths of monotone subsequences in a Mallows permutation
- Mallows permutations and finite dependence
- Mallows permutations as stable matchings
- Noisy sorting without resampling
- NON-NULL RANKING MODELS. I
- On the Cutwidth and the Topological Bandwidth of a Tree
- On the cycle structure of Mallows permutations
- On the perfect orderability of unions of two graphs
- On the Problem of Decomposing a Graph into n Connected Factors
- On tree width, bramble size, and expansion
- Parameterized algorithms
- Permutations avoiding a pattern of length three under Mallows distributions
- Probability and Computing
- Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
- Rank-width of random graphs
- Sparsity. Graphs, structures, and algorithms
- Tail bounds for sums of geometric and exponential variables
- Tangled paths: a random graph model from Mallows permutations (extended abstract)
- The length of the longest increasing subsequence of a random Mallows permutation
- The probability of avoiding consecutive patterns in the Mallows distribution
- The Treewidth and Pathwidth of Graph Unions
- Thermodynamic limit for the Mallows model on S_n
- Treewidth. Computations and approximations
This page was built for publication: Tangled paths: a random graph model from Mallows permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6977157)
