_ 1, isoperimetric inequalities for graphs, and superconcentrators

DOI10.1016/0095-8956(85)90092-9zbMATH Open0549.05051OpenAlexW1993111701WikidataQ97007892 ScholiaQ97007892MaRDI QIDQ800384FDOQ800384

Authors: Noga Alon, Vitali Milman 

Publication date: 1985

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(85)90092-9

Recommendations

• \(\lambda_{\infty}\), vertex isoperimetry and concentration
• Isoperimetric inequalities for graphs
• Isoperimetric inequalities, growth, and the spectrum of graphs
• Isoperimetric inequalities and the width parameters of graphs
• Weighted graph Laplacians and isoperimetric inequalities
• On the isoperimetric spectrum of graphs and its approximations
• The Faber-Krahn type isoperimetric inequalities for a graph
• Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
• Isoperimetric inequalities in graphs and surfaces
• Sufficient conditions for graphs to be λ′‐optimal and super‐λ′

zbMATH Keywords

asymptotic isoperimetric inequalitiesLaplace operator of a graphlinear sized expandersSpectra of Graphssuperconcentrators

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Global versus local asymptotic theories of finite-dimensional normed spaces
• Connection of the dual space of a group with the structure of its closed subgroups
• Title not available (Why is that?)
• Filling Riemannian manifolds
• Spectra of Cayley graphs
• Title not available (Why is that?)
• A short proof for a theorem of Harper about Hamming-spheres
• Explicit Concentrators from Generalized N-Gons
• Optimal numberings and isoperimetric problems on graphs
• Title not available (Why is that?)
• A Topological Application of the Isoperimetric Inequality
• Sorting in \(c \log n\) parallel steps
• Title not available (Why is that?)
• Lower Bounds for the Partitioning of Graphs
• Title not available (Why is that?)
• On the bipartition of graphs
• Explicit constructions of linear-sized superconcentrators
• Cubic graphs on \(\leq 14\) vertices
• Spectra of graphs with transitive groups
• Better expanders and superconcentrators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Title not available (Why is that?)
• Unconditional and symmetric sets in \(n\)-dimensional normed spaces
• A quantitative finite-dimensional Krivine theorem
• A note on a construction of Margulis
• Ergodic theory, group representations, and rigidity
• Title not available (Why is that?)
• Extremal Configurations on a Discrete Torus and a Generalization of the Generalized Macaulay Theorem
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• Large regular bipartite graphs with median eigenvalue 1
• The spectrum of Platonic graphs over finite fields
• Discrete quantitative nodal theorem
• Secure fast evaluation of iterative methods: with an application to secure PageRank
• The clustering coefficient and the diameter of small-world networks
• Dependence ordering for Markov processes on partially ordered spaces
• On Dinur’s proof of the PCP theorem
• Eigenvalues and diameter
• Optimization problems for weighted graphs and related correlation estimates
• On Khot’s unique games conjecture
• A stability result for balanced dictatorships in \(S_n\)
• Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
• A lower bound on the area of permutation layouts
• Random Latin square graphs
• Large degree covers and sharp resonances of hyperbolic surfaces
• Spectra of graphs and fractal dimensions. I
• The limit of first eigenfunctions of the \(p\)-Laplacian on graphs
• Some observations on the smallest adjacency eigenvalue of a graph
• Diffusion operator and spectral analysis for directed hypergraph Laplacian
• Diameters, distortion, and eigenvalues
• \(\lambda_{\infty}\), vertex isoperimetry and concentration
• Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate
• The rapid mixing of random walks defined by an \(n\)-cube
• A global Poincaré inequality on graphs via a conical curvature-dimension condition
• Isoperimetric numbers of graph bundles
• Shortest paths in distance-regular graphs
• Eigenvalues and separation in graphs
• Evaluating performance of image segmentation criteria and techniques
• On the structure of isometrically embeddable metric spaces
• Boundary graphs. II: The limit case of a spectral property
• On middle cube graphs
• Stochastic completeness of graphs: bounded Laplacians, intrinsic metrics, volume growth and curvature
• Multi-way dual Cheeger constants and spectral bounds of graphs
• Design of highly synchronizable and robust networks
• Random Walks on Randomly Evolving Graphs
• Expanding and forwarding
• Bounding the diameter and the mean distance of a graph from its eigenvalues: Laplacian versus adjacency matrix methods
• Metric uniformization and spectral bounds for graphs
• Graph Laplacians, nodal domains, and hyperplane arrangements
• Martingales, Poincaré type inequalities, and deviation inequalities
• Testing Expansion in Bounded-Degree Graphs
• Synchronization of coupled chaotic maps
• Extremal results for odd cycles in sparse pseudorandom graphs
• Graphs with given diameter maximizing the algebraic connectivity
• Strong isoperimetric inequality for tessellating quantum graphs
• On edge-rupture degree of graphs
• Intrinsic isoperimetry of the giant component of supercritical bond percolation in dimension two
• LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
• Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?
• The Cheeger cut and Cheeger problem in metric graphs
• Modular orientations of random and quasi-random regular graphs
• A lattice point problem and additive number theory
• Property \(F\ell_q\) implies property \(F\ell_{p}\) for \(1<p<q<\infty\)
• On the spectrum of the sum of generators for a finitely generated group
• On testing expansion in bounded-degree graphs
• Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments
• Multi-way spectral partitioning and higher-order Cheeger inequalities
• Simplicial complexes: spectrum, homology and random walks
• Spectral estimates for infinite quantum graphs
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Magnetic-sparseness and Schrödinger operators on graphs
• Spectral and combinatorial properties of some algebraically defined graphs
• A quasi-stability result for dictatorships in \(S_n\)
• Spectral gap estimates in mean field spin glasses
• Heegaard splittings, the virtually Haken conjecture and property \((\tau)\)
• Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
• Concentration of normalized sums and a central limit theorem for noncorrelated random variables
• The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
• The alternating polynomials and their relation with the spectra and conditional diameters of graphs
• Spectrum and combinatorics of two-dimensional Ramanujan complexes
• Generalizing the hypergraph Laplacian via a diffusion process with mediators
• Intrinsic Metrics on Graphs: A Survey
• Algebraic connectivity of directed graphs
• Pseudorandom generators for combinatorial checkerboards
• Eigenvalues and expanders
• Expansion in \(\text{SL}_d(\mathbb Z/q\mathbb Z)\), \(q\) arbitrary.
• The influence of Miroslav Fiedler on spectral graph theory
• On Laplacians of random complexes
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• A new upper bound for the isoperimetric number of de Bruijn networks
• Ramanujan complexes and high dimensional expanders
• Title not available (Why is that?)
• Diameters and Eigenvalues
• Some geometric aspects of graphs and their eigenfunctions
• Variants of Kazhdan's property for subgroups of semisimple groups
• Sums and products along sparse graphs
• Title not available (Why is that?)
• Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
• A bipartite analogue of Dilworth's theorem
• A domain monotonicity theorem for graphs and Hamiltonicity
• Expansion in \(\mathrm{SL}_d(\mathcal O_K/I)\), \(I\) square-free.
• A Cheeger-type inequality on simplicial complexes
• Current research on algebraic combinatorics. Supplements to our book, Algebraic combinatorics I
• A spectral bound for vertex-transitive graphs and their spanning subgraphs
• Laplacian matrices of graphs: A survey
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• A computational study of graph partitioning
• Compressions and isoperimetric inequalities
• Evolving sets, mixing and heat kernel bounds

This page was built for publication: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

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