Tangled Paths: A Random Graph Model from Mallows Permutations

MaRDI QIDQ6505169arXivFDO

Authors Jessica Enright, Kitty Meeks, William Pettersson, John Sylvester

Published in arXiv

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We introduce the random graph $mathcalP(n,q)$ which results from taking the union of two paths of length $ngeq1$, where the vertices of one of the paths have been relabelled according to a Mallows permutation with real parameter $0<q(n)leq1$. 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 $mathcalP(n,q)$ we determine the treewidth and cutwidth of $mathcalP(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$.

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 Q6505169)