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

DOI10.1016/0095-8956(85)90092-9zbMath0549.05051WikidataQ97007892 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

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C99: Graph theory

Related Items

Local Expansion of Symmetrical Graphs, Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow, On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs, The bisection width of cubic graphs, Eigenvalues of Graphs and Sobolev Inequalities, Unnamed Item, Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments, Algebraic connectivity of directed graphs, Dependence ordering for Markov processes on partially ordered spaces, Expansion and Lack Thereof in Randomly Perturbed Graphs, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Laplace eigenvalues of graphs---a survey, Compressions and isoperimetric inequalities, Lower bounds of the Laplacian spectrum of graphs based on diameter, A bipartite analogue of Dilworth's theorem, Modified logarithmic Sobolev inequalities in discrete settings, Spectral partitioning works: planar graphs and finite element meshes, The spectrum of Platonic graphs over finite fields, Old and new results on algebraic connectivity of 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, Explicit construction of linear sized tolerant networks, Eigenvalues and expanders, Approximate counting, uniform generation and rapidly mixing Markov chains, Spectra of graphs and fractal dimensions. I, Eigenvalues, diameter, and mean distance in graphs, On the second eigenvalue of a graph, Optimal linear labelings and eigenvalues of graphs, A domain monotonicity theorem for graphs and Hamiltonicity, Eigenvalues and separation in graphs, On the spectrum of the sum of generators for a finitely generated group, 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, Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?, 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, Laplacian matrices of graphs: A survey, Hash functions and Cayley graphs, A computational study of graph partitioning, Recursive construction for 3-regular expanders, The alternating polynomials and their relation with the spectra and conditional diameters of graphs, Expansion properties of Cayley graphs of the alternating groups, Semidefinite programming in combinatorial optimization, From local adjacency polynomials to locally pseudo-distance-regular graphs, A new upper bound for the isoperimetric number of de Bruijn networks, Boundary graphs. II: The limit case of a spectral property, Concentration of normalized sums and a central limit theorem for noncorrelated random variables, Expanding and forwarding, 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, On graphs whose second largest eigenvalue does not exceed \((\sqrt {5}-1)/2\), The rapid mixing of random walks defined by an \(n\)-cube, Graph Laplacians, nodal domains, and hyperplane arrangements, Tough Ramsey graphs without short cycles, A lattice point problem and additive number theory, Isoperimetric numbers of graph bundles, Simulating BPP using a general weak random source, Shortest paths in distance-regular graphs, Heegaard splittings, the virtually Haken conjecture and property \((\tau)\), Logarithmic reduction of the level of randomness in some probabilistic geometric constructions, Explicit construction of linear sized tolerant networks. (Reprint), Enumeration and random walks on finite groups, On random random walks, Logarithmic Sobolev inequalities for finite Markov chains, 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, Isoperimetric numbers of graphs, On Dinur’s proof of the PCP theorem, NON-BACKTRACKING RANDOM WALKS MIX FASTER, Isoperimetric Problem and Meta-fibonacci Sequences, Expander graphs and their applications, Expanders and Diffusers, Diameters and Eigenvalues

Cites Work