Degree sequence of random permutation graphs

DOI10.1214/16-AAP1207MaRDI QIDQ525301zbMATH OpenOpenAlexFDO

Authors Bhaswar B. Bhattacharya, Sumit Mukherjee

Publication date 3 May 2017

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.03582

zbMATH Keywords

limit theoremsgraph limitcombinatorial probabilitypermutation limitMallow's model

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Combinatorial probability (60C05)

Abstract: In this paper we study the degree sequence of the permutation graph $G_{p{i}_n}$ associated with a sequence $p{i}_{n}in{S}_n$ of random permutations. Joint limiting distributions of the degrees are established using results from graph and permutation limit theories. In particular, for the uniform random permutation, the joint distribution of the degrees of the vertices labelled $lceiln{r}_{1}ceil,lceiln{r}_{2}ceil,ldots,lceiln{r}_{s}ceil$ converges (after scaling by $n$) to independent random variables $D_1,D_2,ldots,D_s$, where $D_{i}simextUnif(r_i,1-r_i)$, for $r_{i}in[0,1]$ and $iin1,2,ldots,s$. Moreover, the degree of the mid-vertex (the vertex labelled $n/2$) has a central limit theorem, and the minimum degree converges to a Rayleigh distribution after appropriate scalings. Finally, the limiting degree distribution of the permutation graph associated with a Mallows random permutation is determined, and interesting phase transitions are observed. Our results extend to other exponential measures on permutations.

Recommendations

• Random graphs with a given degree sequence
• Degree sequences of random digraphs and bipartite graphs
• Degree sequence of a scale-free random graph
• The number of graphs and a random graph with a given degree sequence
• Quasi‐random graphs with given degree sequences
• Random permutation graphs and related Markov chains
• scientific article; zbMATH DE number 713480
• Degree sequences in graphs
• Degree sequences of sufficiently dense random uniform hypergraphs
• The degree sequence of random graphs from subcritical classes

Cited in

(8)

• Random permutation graphs and related Markov chains
• The random transposition dynamics on random regular graphs and the Gaussian free field
• On random trees obtained from permutation graphs
• Statistical enumeration of groups by double cosets
• Thresholds for patterns in random permutations with a given number of inversions
• The permuton limit of random recursive separable permutations
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Random Generation and Enumeration of Bipartite Permutation Graphs

This page was built for publication: Degree sequence of random permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q525301)