_ 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)

• 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
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• On graphs whose second largest eigenvalue does not exceed \((\sqrt {5}-1)/2\)
• Tough Ramsey graphs without short cycles
• Expansion of random graphs: new proofs, new results
• Graph-theoretic design and analysis of key predistribution schemes
• Semidefinite programming in combinatorial optimization
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Explicit construction of linear sized tolerant networks
• Approximate counting, uniform generation and rapidly mixing Markov chains
• On the spectrum and linear programming bound for hypergraphs
• Lower bounds of the Laplacian spectrum of graphs based on diameter
• Modified logarithmic Sobolev inequalities in discrete settings
• Coboundary expanders
• Laplace eigenvalues of graphs---a survey
• Title not available (Why is that?)
• Expansion in finite simple groups of Lie type.
• On the spectral gap of a quantum graph
• Old and new results on algebraic connectivity of graphs
• Linear programming bounds for regular graphs
• Eigenvalues and linear quasirandom hypergraphs
• Uniform positivity improving property, Sobolev inequalities, and spectral gaps
• Enumeration and random walks on finite groups
• Mixing in high-dimensional expanders
• On the second eigenvalue of a graph
• Spectral partitioning works: planar graphs and finite element meshes
• General Cheeger inequalities for \(p\)-Laplacians on graphs
• Logarithmic Sobolev, isoperimetry and transport inequalities on graphs
• Concentration on the discrete torus using transportation
• Around quasidiagonal operators
• Fighting constrained fires in graphs
• Isoperimetric numbers of graphs
• Counting problems in Apollonian packings
• The expansion and mixing time of skip graphs with applications
• Eigenvalues, diameter, and mean distance in graphs
• A sample of samplers: a computational perspective on sampling
• Cutoff on all Ramanujan graphs
• On the spectrum of the generalised Petersen graphs
• Glauber dynamics for the mean-field Potts model
• Simulating BPP using a general weak random source
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
• Isoperimetric inequalities in simplicial complexes
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
• Small-diameter Cayley graphs for finite simple groups
• The chromatic number of random Cayley graphs
• Eigenvalues of Graphs and Sobolev Inequalities
• A spectral lower bound for the treewidth of a graph and its consequences
• Candidate one-way functions based on expander graphs
• Expander graphs and their applications
• Optimal linear labelings and eigenvalues of graphs
• On hyperboundedness and spectrum of Markov operators
• Hash functions and Cayley graphs
• Logarithmic Sobolev inequalities for finite Markov chains
• The bisection width of cubic graphs
• A low-memory algorithm for finding short product representations in finite groups.
• Expansion in perfect groups.
• Spectra of lifted Ramanujan graphs
• The Ramanujan conjecture and its applications
• Rational realizations of the minimum rank of a sign pattern matrix
• An introduction to the Ribe program
• Cheeger inequalities for unbounded graph Laplacians
• An isoperimetric inequality for conjugation-invariant sets in the symmetric group
• Limits of locally-globally convergent graph sequences
• 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

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)