Expansion and Lack Thereof in Randomly Perturbed Graphs

DOI10.1007/978-3-540-78808-9_3zbMath1142.68310OpenAlexW2108797586MaRDI QIDQ5900217

Abraham D. Flaxman

Publication date: 19 August 2008

Published in: Algorithms and Models for the Web-Graph (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.im/1243430603

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A Geometric Preferential Attachment Model of Networks II

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• The eigenvalues of random symmetric matrices
• Eigenvalues of random power law graphs
• On the scaling of the chemical distance in long-range percolation models
• The diameter of long-range percolation clusters on finite cycles
• The diameter of a long-range percolation graph
• The small-world phenomenon
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• On smoothed analysis in dense graphs and formulas
• A proof of alon's second eigenvalue conjecture
• The Diameter of a Cycle Plus a Random Matching
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Adding random edges to dense graphs
• How many random edges make a dense graph hamiltonian?
• Smoothed analysis of algorithms
• Algorithms and Models for the Web-Graph
• Algorithms and Models for the Web-Graph
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Spectral techniques applied to sparse random graphs
• Collective dynamics of ‘small-world’ networks
• High Degree Vertices and Eigenvalues in the Preferential Attachment Graph