Name
Title | ||
|---|---|---|
On the connected components of a random permutation graph with a given number of edges |
Abstract | ||
|---|---|---|
A permutation @s of [n] induces a graph G"@s on [n] - its edges are inversion pairs in @s. The graph G"@s is connected if and only if @s is indecomposable. Let @s(n,m) denote a permutation chosen uniformly at random among all permutations of [n] with m inversions. Let p(n,m) be the common value for the probabilities P(@s(n,m) is indecomposable) and P(G"@s"("n","m") is connected). We prove that p(n,m) is non-decreasing with m by constructing a Markov process {@s(n,m)} in which @s(n,m+1) is obtained by increasing one of the components of the inversion sequence of @s(n,m) by one. We show that, with probability approaching 1, G"@s"("n","m") becomes connected for m asymptotic to m"n=(6/@p^2)nlogn. We also find the asymptotic sizes of the largest and smallest components when the number of edges is moderately below the threshold m"n. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jcta.2013.07.010 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
markov process,random permutation graph,probabilities p,inversion pair,inversion sequence,connected component,common value,asymptotic size,m inversion,graph g,threshold m,m asymptotic,permutation graph,inversion,random permutation | Permutation graph,Discrete mathematics,Graph,Combinatorics,Markov process,Permutation,Random permutation,Connected component,Indecomposable module,Mathematics | Journal |
Volume | Issue | ISSN |
120 | 8 | Journal of Combinatorial Theory, Series A 120 (2013), 1947-1975 |
Citations | PageRank | References |
2 | 0.39 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hüseyin Acan | 1 | 6 | 1.86 |
| BORIS PITTEL | 2 | 621 | 135.03 |