2019/01/20 by Oğuz Gürerk, Ümi̇t Işlak, Ümit Işlak +4 · 1 citation
Computer Science · Mathematics · #05C80 #1-planar graph #60C05 #Advanced Combinatorial Mathematics #Chordal graph #Combinatorics #Combinatorics (math.CO) #Degree (music) #Discrete mathematics #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics #Permutation (music) #Permutation graph #Physics #Probability (math.PR) #Random graph #Random permutation #Random regular graph #Symmetric group #Trapezoid graph #math.CO #math.PR #msc:05C80 #msc:60C05
paper · pdf · doi:10.48550/arxiv.1901.06678
published in arXiv (Cornell University) (Cornell University) · 21 pages, 1 figure
openalex publication_date 2019/01/20 · arxiv created 2021/07/29 · arxiv updated 2021/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a given permutation πn in Sn, a random permutation graph is formed by including an edge between two vertices i and j if and only if (i - j) (πn(i) - πn (j)) < 0. In this paper, we study various statistics of random permutation graphs. In particular, the degree of a given node, the number of nodes with a given degree, the number of isolated vertices, and the number of cliques are analyzed. Further, explicit formulas for the probabilities of having a given number of connected components and isolated vertices are obtained.