Permutation pseudographs and contiguity

Catherine Greenhill, Svante Janson, Jeong Han Kim, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation σ of {1, 2,..., n} uniformly at random and taking the n edges {i, σ(i)}. We prove several contiguity results involving permutation pseudographs (contiguity is a kind of asymptotic equivalence of sequences of probability spaces). Namely, we show that a random 4-regular pseudograph is contiguous with the sum of two permutation pseudographs, the sum of a permutation pseudograph and a random Hamilton cycle, and the sum of a permutation pseudograph and a random 2-regular pseudograph. (The sum of two random pseudograph spaces is defined by choosing a pseudograph from each space independently and taking the union of the edges of the two pseudographs. ) All these results are proved simultaneously by working in a general setting, where each cycle of the permutation is given a nonnegative constant multiplicative weight. A further contiguity result is proved involving the union of a weighted permutation pseudograph and a random regular graph of arbitrary degree. All corresponding results for simple graphs are obtained as corollaries.

Original languageEnglish
Pages (from-to)273-298
Number of pages26
JournalCombinatorics Probability and Computing
Volume11
Issue number3
DOIs
Publication statusPublished - May 2002
Externally publishedYes

Cite this