_ 1, isoperimetric inequalities for graphs, and superconcentrators

DOI10.1016/0095-8956(85)90092-9MaRDI QIDQ800384zbMATH OpenOpenAlexWikidataFDO

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

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)

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‐λ′

Cites work

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

Cited in

(only showing first 100 items - show all)

• Concentration on the discrete torus using transportation
• Compressions and isoperimetric inequalities
• Expansion in finite simple groups of Lie type.
• Old and new results on algebraic connectivity of graphs
• Mixing in high-dimensional expanders
• The Ramanujan conjecture and its applications
• Cheeger inequalities for unbounded graph Laplacians
• Evolving sets, mixing and heat kernel bounds
• On the spectrum and linear programming bound for hypergraphs
• Current research on algebraic combinatorics. Supplements to our book, Algebraic combinatorics I
• On graphs whose second largest eigenvalue does not exceed \((\sqrt {5}-1)/2\)
• Cutoff on all Ramanujan graphs
• On the spectrum of the generalised Petersen graphs
• Intrinsic Metrics on Graphs: A Survey
• A Cheeger-type inequality on simplicial complexes
• The expansion and mixing time of skip graphs with applications
• The chromatic number of random Cayley graphs
• Linear programming bounds for regular graphs
• Isoperimetric inequalities in simplicial complexes
• A new upper bound for the isoperimetric number of de Bruijn networks
• Eigenvalues of Graphs and Sobolev Inequalities
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• A bipartite analogue of Dilworth's theorem
• Lower bounds of the Laplacian spectrum of graphs based on diameter
• Modified logarithmic Sobolev inequalities in discrete settings
• Tough Ramsey graphs without short cycles
• Coboundary expanders
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• On hyperboundedness and spectrum of Markov operators
• Variants of Kazhdan's property for subgroups of semisimple groups
• Algebraic connectivity of directed graphs
• Candidate one-way functions based on expander graphs
• Pseudorandom generators for combinatorial checkerboards
• Logarithmic Sobolev inequalities for finite Markov chains
• Expansion of random graphs: new proofs, new results
• Eigenvalues and expanders
• A spectral lower bound for the treewidth of a graph and its consequences
• An introduction to the Ribe program
• Expansion in perfect groups.
• Around quasidiagonal operators
• Glauber dynamics for the mean-field Potts model
• Ramanujan complexes and high dimensional expanders
• Uniform positivity improving property, Sobolev inequalities, and spectral gaps
• Some geometric aspects of graphs and their eigenfunctions
• Sums and products along sparse graphs
• Fighting constrained fires in graphs
• Expansion in \(\text{SL}_d(\mathbb Z/q\mathbb Z)\), \(q\) arbitrary.
• Eigenvalues, diameter, and mean distance in graphs
• The influence of Miroslav Fiedler on spectral graph theory
• Hash functions and Cayley graphs
• A domain monotonicity theorem for graphs and Hamiltonicity
• Expander graphs and their applications
• Graph-theoretic design and analysis of key predistribution schemes
• On the second eigenvalue of a graph
• A computational study of graph partitioning
• A low-memory algorithm for finding short product representations in finite groups.
• Optimal linear labelings and eigenvalues of graphs
• The bisection width of cubic graphs
• Isoperimetric numbers of graphs
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
• On the spectral gap of a quantum graph
• Spectral partitioning works: planar graphs and finite element meshes
• Eigenvalues and linear quasirandom hypergraphs
• scientific article; zbMATH DE number 4193718 (Why is no real title available?)
• Rational realizations of the minimum rank of a sign pattern matrix
• Laplace eigenvalues of graphs---a survey
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• scientific article; zbMATH DE number 878889 (Why is no real title available?)
• Semidefinite programming in combinatorial optimization
• Simulating BPP using a general weak random source
• scientific article; zbMATH DE number 2133152 (Why is no real title available?)
• Counting problems in Apollonian packings
• Diameters and Eigenvalues
• A sample of samplers: a computational perspective on sampling
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
• Enumeration and random walks on finite groups
• General Cheeger inequalities for \(p\)-Laplacians on graphs
• Logarithmic Sobolev, isoperimetry and transport inequalities on graphs
• A spectral bound for vertex-transitive graphs and their spanning subgraphs
• Spectra of lifted Ramanujan graphs
• Explicit construction of linear sized tolerant networks
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
• Limits of locally-globally convergent graph sequences
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Laplacian matrices of graphs: A survey
• An isoperimetric inequality for conjugation-invariant sets in the symmetric group
• Expansion in \(\mathrm{SL}_d(\mathcal O_K/I)\), \(I\) square-free.
• Small-diameter Cayley graphs for finite simple groups
• The rapid mixing of random walks defined by an \(n\)-cube
• Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments
• On Khot’s unique games conjecture
• A lower bound on the area of permutation layouts
• Multi-way dual Cheeger constants and spectral bounds of graphs
• Spectra of graphs and fractal dimensions. I
• A global Poincaré inequality on graphs via a conical curvature-dimension condition
• Optimization problems for weighted graphs and related correlation estimates
• Magnetic-sparseness and Schrödinger operators on graphs
• On the spectrum of the sum of generators for a finitely generated group
• The spectrum of Platonic graphs over finite fields

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)