TY - JOUR

T1 - Permutation pseudographs and contiguity

AU - Greenhill, Catherine

AU - Janson, Svante

AU - Kim, Jeong Han

AU - Wormald, Nicholas C.

PY - 2002/5

Y1 - 2002/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036590598&partnerID=8YFLogxK

U2 - 10.1017/S0963548301005065

DO - 10.1017/S0963548301005065

M3 - Article

AN - SCOPUS:0036590598

VL - 11

SP - 273

EP - 298

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 3

ER -