Random induced subgraphs of Cayley graphs induced by transpositions

DOI10.1016/J.DISC.2011.07.027MaRDI QIDQ409364zbMATH OpenOpenAlexFDO

Authors Emma Yu Jin, Christian M. Reidys

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationrandom graphtranspositiongiant componentvertex boundary

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: In this paper we study random induced subgraphs of Cayley graphs of the symmetric group induced by an arbitrary minimal generating set of transpositions. A random induced subgraph of this Cayley graph is obtained by selecting permutations with independent probability, $lambd{a}_n$. Our main result is that for any minimal generating set of transpositions, for probabilities $lambd{a}_n=frac1+epsilo{n}_{n}n-1$ where $n^{-1/3+delta}leepsilo{n}_n<1$ and $delta>0$, a random induced subgraph has a.s. a unique largest component of size $wp(epsilo{n}_n)frac1+epsilo{n}_{n}n-1n!$, where $wp(epsilo{n}_n)$ is the survival probability of a specific branching process.

Recommendations

• Random subgraphs of Cayley graphs over p-groups
• On Cayley graphs on the symmetric group generated by transpositions
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• On the girth of random Cayley graphs
• On subgraphs of random Cayley sum graphs

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 5722221 (Why is no real title available?)
• scientific article; zbMATH DE number 736289 (Why is no real title available?)
• scientific article; zbMATH DE number 4113631 (Why is no real title available?)
• scientific article; zbMATH DE number 3801574 (Why is no real title available?)
• scientific article; zbMATH DE number 3313418 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A group-theoretic model for symmetric interconnection networks
• Embedding longest fault-free paths onto star graphs with more vertex faults
• Estimating the expected reversal distance after a fixed number of reversals
• Estimating true evolutionary distances between genomes
• Experimental and statistical analysis of sorting by reversals
• Hamiltonian-laceability of star graphs
• Hyper Hamiltonian laceability on edge fault star graph
• Hyper hamiltonian laceability of Cayley graphs generated by transpositions
• Large components in random induced subgraphs of \(n\)-cubes
• Largest random component of a k-cube
• Limiting behavior for the distance of a random walk
• Longest fault-free paths in star graphs with vertex faults
• Minimal factorizations of permutations into star transpositions
• On the fault-diameter of the star graph
• Random graph dynamics
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees
• Reliable broadcasting in hypercubes with random link and node failures
• Strong uniform times and finite random walks
• The Evolution of Random Subgraphs of the Cube
• Transforming cabbage into turnip

Cited in

(2)

• Topological classification and enumeration of RNA structures by genus
• Random subgraphs of Cayley graphs over p-groups

This page was built for publication: Random induced subgraphs of Cayley graphs induced by transpositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409364)