Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem.
Landau, Zeph, Russell, Alexander (2004)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Displaying similar documents to “Improved expansion of random Cayley graphs.”
Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem.
Upper bounds on the non-3-colourability threshold of random graphs.
Fountoulakis, Nikolaos, McDiarmid, Colin (2002)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Entrywise bounds for eigenvectors of random graphs.
Mitra, Pradipta (2009)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
The sizes of components in random circle graphs
Ramin Imany-Nabiyyi (2008)
Discussiones Mathematicae Graph Theory
Similarity:
We study random circle graphs which are generated by throwing n points (vertices) on the circle of unit circumference at random and joining them by an edge if the length of shorter arc between them is less than or equal to a given parameter d. We derive here some exact and asymptotic results on sizes (the numbers of vertices) of "typical" connected components for different ways of sampling them. By studying the joint distribution of the sizes of two components, we "go into" the structure...
Paths of specified length in random -partite graphs.
Subramanian, C.R. (2001)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Compositions of random functions on a finite set.
Dalal, Avinash, Schmutz, Eric (2002)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
The diameter and Laplacian eigenvalues of directed graphs.
Chung, Fan (2006)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Asymptotic properties of random graphs
Zbigniew Palka
Similarity:
CONTENTS1. Introduction...........................................................................5 1.1. Purpose and scope..........................................................5 1.2. Probability-theoretic preliminaries....................................6 1.3. Graphs............................................................................11 1.4. Random graphs..............................................................132. Vertex-degrees....................................................................15 2.1....
On pendant vertices in random graphs
Zbigniew Palka (1981)
Colloquium Mathematicae
Similarity:
On vertex, edge, and vertex-edge random graphs.
Beer, Elizabeth, Fill, James Allen, Janson, Svante, Scheinerman, Edward R. (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Expansion in finite simple groups of Lie type
Emmanuel Breuillard, Ben J. Green, Robert Guralnick, Terence Tao (2015)
Journal of the European Mathematical Society
Similarity:
We show that random Cayley graphs of finite simple (or semisimple) groups of Lie type of fixed rank are expanders. The proofs are based on the Bourgain-Gamburd method and on the main result of our companion paper [BGGT].
A random graph model for power law graphs.
Aiello, William, Chung, Fan, Lu, Linyuan (2001)
Experimental Mathematics
Similarity:
Random walks on finite groups with few random generators.
Pak, Igor (1999)
Electronic Journal of Probability [electronic only]
Similarity:
Discrepancy and eigenvalues of Cayley graphs
Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht (2016)
Czechoslovak Mathematical Journal
Similarity:
We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This affirmatively answers a question of Chung and Graham (2002) for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.