Geodesic
Tangled paths: a random graph model from Mallows permutations
Jessica Enright1 ; Kitty Meeks1 ; William Pettersson1 ; John Sylvester1
1School of Computing Science, University of Glasgow, Glasgow, UK
The electronic journal of combinatorics, Tome 32 (2025) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We introduce the random graph $\mathcal{P}(n,q)$ which results from taking the union of two paths of length $n\geq 1$, where the vertices of one of the paths have been relabelled according to a Mallows permutation with real parameter $0. 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$.
DOI : 10.37236/11602
Classification : 05C80, 05A05, 68Q87, 05C78, 05C38
Mots-clés : tangled path, Mallows permutation

Jessica Enright  1   ; Kitty Meeks  1   ; William Pettersson  1   ; John Sylvester  1

1 School of Computing Science, University of Glasgow, Glasgow, UK 
@article{10_37236_11602,
     author = {Jessica Enright and Kitty Meeks and William Pettersson and John Sylvester},
     title = {Tangled paths: a random graph model from {Mallows} permutations},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {2},
     doi = {10.37236/11602},
     zbl = {1569.05322},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11602/}
}
TY  - JOUR
AU  - Jessica Enright
AU  - Kitty Meeks
AU  - William Pettersson
AU  - John Sylvester
TI  - Tangled paths: a random graph model from Mallows permutations
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11602/
DO  - 10.37236/11602
ID  - 10_37236_11602
ER  - 
%0 Journal Article
%A Jessica Enright
%A Kitty Meeks
%A William Pettersson
%A John Sylvester
%T Tangled paths: a random graph model from Mallows permutations
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11602/
%R 10.37236/11602
%F 10_37236_11602
Jessica Enright; Kitty Meeks; William Pettersson; John Sylvester. Tangled paths: a random graph model from Mallows permutations. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/11602

Cité par Sources :