Random induced subgraphs of Cayley graphs induced by transpositions

DOI10.1016/J.DISC.2011.07.027zbMATH Open1239.05089arXiv0909.4037OpenAlexW2051144681MaRDI QIDQ409364FDOQ409364

Authors: Emma Yu Jin, Christian M. Reidys 

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graph dynamics
• A group-theoretic model for symmetric interconnection networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong uniform times and finite random walks
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Hyper Hamiltonian laceability on edge fault star graph
• On the fault-diameter of the star graph
• A phase transition in the random transposition random walk
• The Evolution of Random Subgraphs of the Cube
• Hamiltonian-laceability of star graphs
• Estimating the expected reversal distance after a fixed number of reversals
• Hyper hamiltonian laceability of Cayley graphs generated by transpositions
• Title not available (Why is that?)
• Large components in random induced subgraphs of \(n\)-cubes
• Transforming cabbage into turnip
• Largest random component of a k-cube
• Minimal factorizations of permutations into star transpositions
• Limiting behavior for the distance of a random walk
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Estimating true evolutionary distances between genomes
• Experimental and statistical analysis of sorting by reversals
• Embedding longest fault-free paths onto star graphs with more vertex faults
• Title not available (Why is that?)
• Longest fault-free paths in star graphs with vertex faults

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)