\(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

DOI10.1016/0095-8956(85)90092-9zbMath0549.05051OpenAlexW1993111701WikidataQ97007892 ScholiaQ97007892MaRDI QIDQ800384

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 inequalities Laplace operator of a graph linear sized expanders Spectra of Graphs superconcentrators

Mathematics Subject Classification ID

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

Related Items

Discrete quantitative nodal theorem, Secure fast evaluation of iterative methods: with an application to secure PageRank, Hash functions and Cayley graphs, Spectral concentration and greedy \(k\)-clustering, The rapid mixing of random walks defined by an \(n\)-cube, A computational study of graph partitioning, Recursive construction for 3-regular expanders, Spectral estimates for infinite quantum graphs, The local limit of the uniform spanning tree on dense graphs, A global Poincaré inequality on graphs via a conical curvature-dimension condition, Graph-theoretic design and analysis of key predistribution schemes, On the spectral gap of a quantum graph, The alternating polynomials and their relation with the spectra and conditional diameters of graphs, General Cheeger inequalities for \(p\)-Laplacians on graphs, Logarithmic Sobolev, isoperimetry and transport inequalities on graphs, Expansion properties of Cayley graphs of the alternating groups, Cutoff on all Ramanujan graphs, Lower bounds of the Laplacian spectrum of graphs based on diameter, On the spectrum of the generalised Petersen graphs, Semidefinite programming in combinatorial optimization, Explicit construction of linear sized tolerant networks, A bipartite analogue of Dilworth's theorem, From local adjacency polynomials to locally pseudo-distance-regular graphs, Eigenvalues and expanders, Modified logarithmic Sobolev inequalities in discrete settings, Spectral gap estimates in mean field spin glasses, Intrinsic isoperimetry of the giant component of supercritical bond percolation in dimension two, Spectral partitioning works: planar graphs and finite element meshes, Approximate counting, uniform generation and rapidly mixing Markov chains, The spectrum of Platonic graphs over finite fields, A new upper bound for the isoperimetric number of de Bruijn networks, Old and new results on algebraic connectivity of graphs, Spectra of graphs and fractal dimensions. I, Boundary graphs. II: The limit case of a spectral property, Graphs with given diameter maximizing the algebraic connectivity, Computing heat kernel PageRank and a local clustering algorithm, The influence of Miroslav Fiedler on spectral graph theory, Pseudorandom generators for combinatorial checkerboards, A Cheeger-type inequality on simplicial complexes, Design of highly synchronizable and robust networks, Linear programming bounds for regular graphs, Expansion in \(\text{SL}_d(\mathbb Z/q\mathbb Z)\), \(q\) arbitrary., Fighting constrained fires in graphs, Diameters, distortion, and eigenvalues, Neumann Cheeger constants on graphs, Small-diameter Cayley graphs for finite simple groups, Isoperimetric inequalities for faces of the cube and the grid, Variants of Kazhdan's property for subgroups of semisimple groups, A lower bound on the area of permutation layouts, Expansion in \(\mathrm{SL}_d(\mathcal O_K/I)\), \(I\) square-free., Ramanujan complexes and high dimensional expanders, Multi-way dual Cheeger constants and spectral bounds of graphs, Eigenvalues, diameter, and mean distance in graphs, Metric uniformization and spectral bounds for graphs, The spectral gap of dense random regular graphs, On edge-rupture degree of graphs, Extremal results for odd cycles in sparse pseudorandom graphs, A low-memory algorithm for finding short product representations in finite groups., On the second eigenvalue of a graph, Spectral and combinatorial properties of some algebraically defined graphs, Expansion of random graphs: new proofs, new results, Expansion in finite simple groups of Lie type., Property \(F\ell_q\) implies property \(F\ell_{p}\) for \(1<p<q<\infty\), On eigenvalues of random complexes, Optimal linear labelings and eigenvalues of graphs, A domain monotonicity theorem for graphs and Hamiltonicity, Eigenvalues of subgraphs of the cube, Size biased couplings and the spectral gap for random regular graphs, On sensitivity of mixing times and cutoff, A quasi-stability result for dictatorships in \(S_n\), Laplace eigenvalues of graphs---a survey, Glauber dynamics for the mean-field Potts model, Sums and products along sparse graphs, Eigenvalues and separation in graphs, Eigenvalues and diameter, Concentration of normalized sums and a central limit theorem for noncorrelated random variables, Spectra of lifted Ramanujan graphs, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly, Expanding and forwarding, Evaluating performance of image segmentation criteria and techniques, Bounds on isoperimetric values of trees, On the spectrum of the sum of generators for a finitely generated group, A spectral lower bound for the treewidth of a graph and its consequences, Martingales, Poincaré type inequalities, and deviation inequalities, Uniform positivity improving property, Sobolev inequalities, and spectral gaps, The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs, Minimum cuts, girth and a spectral threshold, Current research on algebraic combinatorics. Supplements to our book, Algebraic combinatorics I, Weighted expanders and the anisotropic Alon-Boppana theorem, Optimization problems for weighted graphs and related correlation estimates, Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?, On graphs whose second largest eigenvalue does not exceed \((\sqrt {5}-1)/2\), Bounding the diameter and the mean distance of a graph from its eigenvalues: Laplacian versus adjacency matrix methods, On the spectrum, the growth, and the diameter of a graph, Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs, Shallow grates, Around quasidiagonal operators, Compressions and isoperimetric inequalities, Laplacian matrices of graphs: A survey, The diameter of the uniform spanning tree of dense graphs, Optimal Algorithms for Non-Smooth Distributed Optimization in Networks, Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments, Unnamed Item, Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology, On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs, Unnamed Item, Complete Minors in Graphs Without Sparse Cuts, Local Expansion of Symmetrical Graphs, Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow, Expanders and Diffusers, Eigenvalues of Graphs and Sobolev Inequalities, Cheeger estimates of Dirichlet-to-Neumann operators on infinite subgraphs of graphs, Random Walks on Randomly Evolving Graphs, Synchronizability of random rectangular graphs, Algebraic and combinatorial expansion in random simplicial complexes, NON-BACKTRACKING RANDOM WALKS MIX FASTER, Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator, A Markovian and Roe-algebraic approach to asymptotic expansion in measure, Modularity of minor‐free graphs, Generalizing \(p\)-Laplacian: spectral hypergraph theory and a partitioning algorithm, A spectral bound for vertex-transitive graphs and their spanning subgraphs, Combinatorial Fiedler theory and graph partition, Relationships between symmetry-based graph measures, Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions, On the eigenvalues of the graphs \(D(5,q)\), The Cheeger cut and Cheeger problem in metric measure spaces, On the stability of the principal ratio, Graphical designs and gale duality, On the second eigenvalue of random bipartite biregular graphs, Isoperimetric Problem and Meta-fibonacci Sequences, Unnamed Item, Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian, Upper bounds for higher-order Poincaré constants, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Expander graphs and their applications, Forty years of frequent items, Geometric and spectral analysis on weighted digraphs, Graph curvature via resistance distance, Non-planarity of Markoff graphs \(\mod p\), Finding and Using Expanders in Locally Sparse Graphs, Mixing in High-Dimensional Expanders, Sign rank versus Vapnik-Chervonenkis dimension, Vertex Folkman Numbers and the Minimum Degree of Minimal Ramsey Graphs, A Note on Cheeger Inequalities for Piecewise Flat Surfaces, Strong Isoperimetric Inequality for Tessellating Quantum Graphs, Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian, Structure of eigenvectors of random regular digraphs, Graph Clustering using Effective Resistance, Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile, Spectral gap of the discrete Laplacian on triangulations, Formal Zeta function expansions and the frequency of Ramanujan graphs, Growth and expansion in algebraic groups over finite fields, Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery, LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY, Concentration on the Discrete Torus Using Transportation, On the Structure of Isometrically Embeddable Metric Spaces, COBOUNDARY EXPANDERS, Testing Expansion in Bounded-Degree Graphs, Polaritons and excitons: Hamiltonian design for enhanced coherence, An Optimal Algorithm for Decentralized Finite-Sum Optimization, Multi-way spectral partitioning and higher-order cheeger inequalities, Counting problems in Apollonian packings, Existence of the anchored isoperimetric profile in supercritical bond percolation in dimension two and higher, Dependence ordering for Markov processes on partially ordered spaces, Generalizing the hypergraph Laplacian via a diffusion process with mediators, Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks, Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians, Eigenvalue Ratios of Non-Negatively Curved Graphs, Algebraic connectivity of directed graphs, Ramanujan Graphs for Post-Quantum Cryptography, The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs, Expanders with respect to Hadamard spaces and random graphs, Expansion and Lack Thereof in Randomly Perturbed Graphs, Mixing Time of Random Walk on Poisson Geometry Small World, The bisection width of cubic graphs, Outlaw distributions and locally decodable codes, The Ramanujan conjecture and its applications, EIGENVALUES AND LINEAR QUASIRANDOM HYPERGRAPHS, A stability result for balanced dictatorships in S_n, On Middle Cube Graphs, Unnamed Item, On Dinur’s proof of the PCP theorem, An explicit construction of graphs of bounded degree that are far from being Hamiltonian, Experiments with the Markoff Surface, Constructing highly regular expanders from hyperbolic Coxeter groups, Diameters and Eigenvalues, Consensus dynamics on random rectangular graphs, Graph Laplacians, nodal domains, and hyperplane arrangements, Eigenvalues of Cayley graphs, An isoperimetric inequality for conjugation-invariant sets in the symmetric group, The expansion and mixing time of skip graphs with applications, Tough Ramsey graphs without short cycles, On the spectrum and linear programming bound for hypergraphs, Graphs, Vectors, and Matrices, On the Banach-Space-Valued Azuma Inequality and Small-Set Isoperimetry of Alon–Roichman Graphs, Random Latin square graphs, A lattice point problem and additive number theory, Isoperimetric numbers of graphs, Fractal graphs by iterated substitution, Cheeger Inequalities for General Edge-Weighted Directed Graphs, Spectral bounds of directed Cayley graphs of finite groups, Finding Cheeger cuts in hypergraphs via heat equation, Isoperimetric inequalities in simplicial complexes, A new approach to finding the extra connectivity of graphs, On the spectrum of dense random geometric graphs, Magnetic-sparseness and Schrödinger operators on graphs, Stochastic completeness of graphs: bounded Laplacians, intrinsic metrics, volume growth and curvature, Spectra of twists of Cayley and Cayley sum graphs, Isoperimetric numbers of graph bundles, Simulating BPP using a general weak random source, Discrepancies of spanning trees and Hamilton cycles, A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\), Spectrum and combinatorics of two-dimensional Ramanujan complexes, Mean isoperimetry with control on outliers: exact and approximation algorithms, The Cheeger cut and Cheeger problem in metric graphs, Expander construction in \(\mathrm{VNC}^1\), Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, Large degree covers and sharp resonances of hyperbolic surfaces, Expansion in perfect groups., An introduction to the Ribe program, Geometric and spectral properties of directed graphs under a lower Ricci curvature bound, Algebraic connectivity and disjoint vertex subsets of graphs, The clustering coefficient and the diameter of small-world networks, Graphical designs and extremal combinatorics, A generalized Cheeger inequality, Large scale Ricci curvature on graphs, Simplicial complexes: Spectrum, homology and random walks, Multi-way sparsest cut problem on trees with a control on the number of parts and outliers, Large regular bipartite graphs with median eigenvalue 1, Limits of locally-globally convergent graph sequences, Shortest paths in distance-regular graphs, Connectivity and eigenvalues of graphs with given girth or clique number, Modular Orientations of Random and Quasi-Random Regular Graphs, Polynomial-time algorithms for submodular Laplacian systems, Codes, cubes, and graphical designs, The second eigenvalue of some normal Cayley graphs of highly transitive groups, A divide-and-conquer bound for aggregate's quality and algebraic connectivity, Heegaard splittings, the virtually Haken conjecture and property \((\tau)\), Logarithmic reduction of the level of randomness in some probabilistic geometric constructions, Cheeger inequalities for unbounded graph Laplacians, Vertex-connectivity and eigenvalues of graphs, Explicit construction of linear sized tolerant networks. (Reprint), A logician's view of graph polynomials, A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem, A spectral version of the Moore problem for bipartite regular graphs, Cheeger constants, structural balance, and spectral clustering analysis for signed graphs, The chromatic number of random Cayley graphs, The heat flow on metric random walk spaces, A Cheeger type inequality in finite Cayley sum graphs, Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence, Intrinsic Metrics on Graphs: A Survey, Beating treewidth for average-case subgraph isomorphism, Some observations on the smallest adjacency eigenvalue of a graph, The limit of first eigenfunctions of the \(p\)-Laplacian on graphs, The invisible hand of Laplace: the role of market structure in price convergence and oscillation, Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs, A Cheeger cut for uniform hypergraphs, Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions, On Testing Expansion in Bounded-Degree Graphs, Candidate One-Way Functions Based on Expander Graphs, A Sample of Samplers: A Computational Perspective on Sampling, Bravely, Moderately: A Common Theme in Four Recent Works, Basic Facts about Expander Graphs, Semantic Equivalence of Graph Polynomials Definable in Second Order Logic, Cut ratios and Laplacian eigenvalues, Convex structures revisited, Discrepancy and eigenvalues of Cayley graphs, Communicability Angle and the Spatial Efficiency of Networks, Nonpositive curvature is not coarsely universal, Diffusion operator and spectral analysis for directed hypergraph Laplacian, Cheeger inequalities for the discrete magnetic Laplacian, On Khot’s unique games conjecture, On a Cheeger type inequality in Cayley graphs of finite groups, Enumeration and random walks on finite groups, On random random walks, Trivalent expanders, \((\Delta - Y)\)-transformation, and hyperbolic surfaces, Logarithmic Sobolev inequalities for finite Markov chains, Hypergraph expanders from Cayley graphs, Degree of indecomposability of certain highly regular zero-one matrices, Rational realizations of the minimum rank of a sign pattern matrix, Evolving sets, mixing and heat kernel bounds, Random Steiner systems and bounded degree coboundary expanders of every dimension, On hyperboundedness and spectrum of Markov operators, Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate, Spectrum of Johnson graphs, Synchronization of coupled chaotic maps

Cites Work