On the connected components of a random permutation graph with a given number of edges

DOI10.1016/j.jcta.2013.07.010zbMath1278.05221arXiv1211.0246OpenAlexW2049193778MaRDI QIDQ388720

Hüseyin Acan, Boris G. Pittel

Publication date: 6 January 2014

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

inversionrandom permutationconnectivity thresholdpermutation graphindecomposable permutation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Permutations, words, matrices (05A05)

Related Items (4)

Formation of a giant component in the intersection graph of a random chord diagram ⋮ Regenerative random permutations of integers ⋮ Connected chord diagrams and bridgeless maps ⋮ On random trees obtained from permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of indecomposable permutations with a given number of cycles
• Transitivity and connectivity of permutations
• Indecomposable permutations, hypermaps and labeled Dyck paths
• On a likely shape of the random Ferrers diagram
• An asymptotic expansion for the number of permutations with a certain number of inversions
• A combinatorial proof of the log-concavity of a famous sequence counting permutations
• Connected permutation graphs
• Central and local limit theorems applied to asymptotic enumeration
• The Average Number of Stable Matchings
• On the lengths of the pieces of a stick broken at random
• Subgroups of Finite Index in Free Groups

This page was built for publication: On the connected components of a random permutation graph with a given number of edges