✦ LIBER ✦

Random Subgraphs of Cayley Graphs overp-Groups

✍ Scribed by C.M. Reidys

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 146 KB
Volume: 21
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.2000.0421

No coin nor oath required. For personal study only.

✦ Synopsis

The subject of this paper is the size of the largest component in random subgraphs of Cayley graphs, X n , taken over a class of p-groups, G n . G n consists of p-groups, G n , with the following properties:

, where K is some positive constant. We consider Cayley graphs X n = (G n , S n ), where S n = S n ∪ S -1 n , and S n is a minimal G n -generating set. By selecting G n -elements with the independent probability λ n we induce random subgraphs of X n . Our main result is, that there exists a positive constant c > 0 such that for λ n = c ln(|S n |)/|S n | the largest component of random induced subgraphs of X n contains almost all vertices.

📜 SIMILAR VOLUMES

Pancyclic subgraphs of random graphs

✍ Choongbum Lee; Wojciech Samotij 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract An __n__‐vertex graph is called pancyclic if it contains a cycle of length __t__ for all 3≤__t__≤__n__. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if __p__>__n__^−1/2^, then the random graph __G__(__n, p__) a.a.s. satisfies the f

Neighbourhood Graphs of Cayley Graphs fo

Neighbourhood Graphs of Cayley Graphs for Finitely-generated Groups

✍ Markus Neuhauser 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 134 KB

In this short note the neighbourhood graph of a Cayley graph is considered. It has, as nodes, a symmetric generating set of a finitely-generated group . Two nodes are connected by an edge if one is obtained from the other by multiplication on the right by one of the generators. Two necessary conditi

Long cycles in subgraphs of (pseudo)rand

Long cycles in subgraphs of (pseudo)random directed graphs

✍ Ido Ben-Eliezer; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/2 we find a constant __c__ = __c__(γ) such that the following holds. Let __G__ = (__V, E__) be a (pseudo)random directed graph on __n__ vertice

On the Isomorphisms of Cayley Graphs of

On the Isomorphisms of Cayley Graphs of Abelian Groups

✍ Yan-Quan Feng; Yan-Pei Liu; Ming-Yao Xu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 190 KB

Let G be a finite group, S a subset of G=f1g; and let Cay ðG; SÞ denote the Cayley digraph of G with respect to S: If, for any subset T of G=f1g; CayðG; SÞ ffi CayðG; T Þ implies that S a ¼ T for some a 2 AutðGÞ; then S is called a CI-subset. The group G is called a CIM-group if for any minimal gene

Expansion Properties of Cayley Graphs of

Expansion Properties of Cayley Graphs of the Alternating Groups

✍ Yuval Roichman 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 360 KB

Let C be a conjugacy class in the alternating group A n , and let supp(C) be the number of nonfixed digits under the action of a permutation in C. For every 1>$>0 and n 5 there exists a constant c=c($)>0 such that if supp(C) $n then the undirected Cayley graph X(A n , C) is a c expander. A family of

Compound Poisson approximations of subgr

Compound Poisson approximations of subgraph counts in random graphs

✍ Dudley Stark 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 1 views