Eigenvalues and expanders

From MaRDI portal

Publication:1112844

Jump to:navigation, search

DOI10.1007/BF02579166zbMath0661.05053WikidataQ97007656 ScholiaQ97007656MaRDI QIDQ1112844

Publication date: 1986

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

expander eigenvalues of graphs regular bipartite graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Expander graphs (05C48)

Related Items

A Spectral Moore Bound for Bipartite Semiregular Graphs, Spectral gap in random bipartite biregular graphs and applications, Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments, Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices, Unnamed Item, Geometry and Combinatorics via Right-Angled Artin Groups, Unnamed Item, A characterization of the smallest eigenvalue of a graph, Complete Minors in Graphs Without Sparse Cuts, Random Cayley graphs and expanders, Random walks on colored graphs, RECYCLING RANDOM BITS IN PARALLEL, Some inequalities involving the distance signless Laplacian eigenvalues of graphs, Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow, Cheeger Inequalities for General Edge-Weighted Directed Graphs, Rolling backwards can move you forward: On embedding problems in sparse expanders, Unnamed Item, A Note on Even Cycles and Quasirandom Tournaments, Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs, A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, Expanders and Diffusers, The vertex attack tolerance of complex networks, Robustness of random graphs based on graph spectra, Data Analytics on Graphs Part I: Graphs and Spectra on Graphs, On an anti‐Ramsey property of Ramanujan graphs, Near‐perfect token distribution, On the expansion of combinatorial polytopes, A class of scale-free networks with fractal structure based on subshift of finite type, Efficient and Reliable Overlay Networks for Decentralized Federated Learning, CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS, NON-BACKTRACKING RANDOM WALKS MIX FASTER, SYNCHRONIZABILITY AND SYNCHRONIZATION DYNAMICS OF WEIGHED AND UNWEIGHED SCALE FREE NETWORKS WITH DEGREE MIXING, Expander graphs and their applications, Combinatorial Perron values of trees and bottleneck matrices, Finding and Using Expanders in Locally Sparse Graphs, Mixing in High-Dimensional Expanders, Network-complement transitions, symmetries, and cluster synchronization, Sign rank versus Vapnik-Chervonenkis dimension, Simplicial complexes: Spectrum, homology and random walks, Strong Isoperimetric Inequality for Tessellating Quantum Graphs, Expander graphs and gaps between primes, Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian, Finding Critical Links for Closeness Centrality, Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, An Elementary Construction of Constant-Degree Expanders, Formal Zeta function expansions and the frequency of Ramanujan graphs, Ramanujan Graphs in Cryptography, FORCING QUASIRANDOMNESS WITH TRIANGLES, Modular Orientations of Random and Quasi-Random Regular Graphs, Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery, First reformulated Zagreb indices of some classes of graphs, Economical Elimination of Cycles in the Torus, Concentration on the Discrete Torus Using Transportation, Algorithms for #BIS-Hard Problems on Expander Graphs, On the first and second eigenvalue of finite and infinite uniform hypergraphs, COBOUNDARY EXPANDERS, Explicit Bounds from the Alon–Boppana Theorem, Maximum Flows and Minimum Cuts in the Plane, Testing Expansion in Bounded-Degree Graphs, Deterministic Tensor Completion with Hypergraph Expanders, Multi-way spectral partitioning and higher-order cheeger inequalities, Counting problems in Apollonian packings, Construction of expanders and superconcentrators using Kolmogorov complexity, A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem, Many Random Walks Are Faster Than One, Spectra of Extended Double Cover Graphs, Cover matrices of posets and their spectra, A Local Search Algorithm for Branchwidth, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, Generalized quasirandom properties of expanding graph sequences, The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs, Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions, A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma, On Testing Expansion in Bounded-Degree Graphs, Bravely, Moderately: A Common Theme in Four Recent Works, Basic Facts about Expander Graphs, Opinion Forming in Erdös-Rényi Random Graph and Expanders, Local-global convergence, an analytic and structural approach, Combinatorial Algorithms for Distributed Graph Coloring, Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations, ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY, Robustness of regular ring lattices based on natural connectivity, Finite-Time Behavior of Slowly Cooled Annealing Chains, The bisection width of cubic graphs, Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes, High Dimensional Random Walks and Colorful Expansion, On Khot’s unique games conjecture, Eigenvalues and triangles in graphs, EIGENVALUES AND LINEAR QUASIRANDOM HYPERGRAPHS, Measure preserving words are primitive, ON THE DEGREE DISTANCE OF SOME COMPOSITE GRAPHS, Explicit Near-Ramanujan Graphs of Every Degree, Unnamed Item, On Dinur’s proof of the PCP theorem, Unnamed Item, Discrete Graphs – A Paradigm Model for Quantum Chaos, Second largest eigenpair statistics for sparse graphs, Diameters and Eigenvalues, On the bipartiteness constant and expansion of Cayley graphs, Tight products and graph expansion, Embedding graphs with bounded degree in sparse pseudorandom graphs, On the second largest eigenvalue of some Cayley graphs of the symmetric group, Eigenvalues of Cayley graphs, Tough Ramsey graphs without short cycles, On the spectrum and linear programming bound for hypergraphs, Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes, Isoperimetric numbers of graphs, Benjamini-Schramm convergence and spectra of random hyperbolic surfaces of high genus, Spectral bounds of directed Cayley graphs of finite groups, Finding Cheeger cuts in hypergraphs via heat equation, The mixing time of the giant component of a random graph, Isoperimetric inequalities in simplicial complexes, The irregularity of some composite graphs, On the spectral distribution of large weighted random regular graphs, Energy of strong double graphs, Spectra of twists of Cayley and Cayley sum graphs, A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\), Mean isoperimetry with control on outliers: exact and approximation algorithms, On weighted spectral radius of unraveled balls and normalized Laplacian eigenvalues, Expander construction in \(\mathrm{VNC}^1\), Line-graph lattices: Euclidean and non-Euclidean flat bands, and implementations in circuit quantum electrodynamics, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, Expansion in perfect groups., Local Kesten-McKay law for random regular graphs, A Cheeger inequality for graphs based on a reflection principle, Geometric and spectral properties of directed graphs under a lower Ricci curvature bound, Algebraic connectivity and disjoint vertex subsets of graphs, Finding large expanders in graphs: from topological minors to induced subgraphs, Graphical designs and extremal combinatorics, Ramanujan graphs and exponential sums over function fields, Sharp spectral bounds for the vertex-connectivity of regular graphs, Nodal domain count for the generalized graph \(p\)-Laplacian, Commute times for a directed graph using an asymmetric Laplacian, A generalized Cheeger inequality, Graphs with second largest eigenvalue less than 1/2, On the Harary index of graph operations, Aldous' spectral gap property for normal Cayley graphs on symmetric groups, Communication constraints in the average consensus problem, Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs, Branch decomposition heuristics for linear matroids, Multi-way sparsest cut problem on trees with a control on the number of parts and outliers, Limits of locally-globally convergent graph sequences, On the order of regular graphs with fixed second largest eigenvalue, A connection between a question of Bermond and Bollobás and Ramanujan graphs, Polynomial-time algorithms for submodular Laplacian systems, Explicit expanders of every degree and size, Unifying relationships between complexity and stability in mutualistic ecological communities, Combinatorial algorithms for distributed graph coloring, The second eigenvalue of some normal Cayley graphs of highly transitive groups, Maximizing algebraic connectivity for certain families of graphs, On the extreme eigenvalues of regular graphs., Heegaard splittings, the virtually Haken conjecture and property \((\tau)\), Eigenvalues of graphs and a simple proof of a theorem of Greenberg, On some bounds and exact formulae for connective eccentric indices of graphs under some graph operations, Explicit construction of linear sized tolerant networks. (Reprint), Cheeger constants, structural balance, and spectral clustering analysis for signed graphs, Modularity spectra, eigen-subspaces, and structure of weighted graphs, Explicit Construction of Ramanujan Bigraphs, Cycle lengths in expanding graphs, A Cheeger type inequality in finite Cayley sum graphs, Recent progress in combinatorial random matrix theory, Spectral Gap for Complete Graphs: Upper and Lower Estimates, Ramanujan graphs and expander families constructed from \(p\)-ary bent functions, The spectral gap of sparse random digraphs, Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey, The spectral geometry of \(k\)-regular groups, Some observations on the smallest adjacency eigenvalue of a graph, Expanding and forwarding, Spectra of random regular hypergraphs, The invisible hand of Laplace: the role of market structure in price convergence and oscillation, Maximizing the Order of a Regular Graph of Given Valency and Second Eigenvalue, Opinion forming in Erdős-Rényi random graph and expanders, Cut ratios and Laplacian eigenvalues, Perron value and moment of rooted trees, Discrepancy and eigenvalues of Cayley graphs, Bounds on the cover time, Diffusion operator and spectral analysis for directed hypergraph Laplacian, The smallest eigenvalue for reversible Markov chains, The integrity of a cubic graph, Cheeger inequalities for the discrete magnetic Laplacian, Minimum covering reciprocal distance signless Laplacian energy of graphs, Logarithmic Sobolev inequalities for finite Markov chains, On the second eigenvalue of hypergraphs, Derandomized graph products, Evolving sets, mixing and heat kernel bounds, The maximum spectral radius of non-bipartite graphs forbidding short odd cycles, Kissing numbers of regular graphs, A new upper bound on the Cheeger number of a graph, Spectral properties of modularity matrices, Lower bounds for boxicity, Quantum ergodicity on large regular graphs, On hyperboundedness and spectrum of Markov operators, Partitions of networks that are robust to vertex permutation dynamics, Relative expanders, Cycle lengths modulo \(k\) in expanders, New and explicit constructions of unbalanced Ramanujan bipartite graphs, Synchronization of coupled chaotic maps, Resistance distances in Cayley graphs on symmetric groups, Discrete quantitative nodal theorem, On the relationship between the diameter and the size of a boundary of a directed graph, Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling, Secure fast evaluation of iterative methods: with an application to secure PageRank, Explicit spectral gaps for random covers of Riemann surfaces, Inverse expander mixing for hypergraphs, Spectral concentration and greedy \(k\)-clustering, A lower bound for tree resolution, Quantum ergodicity for quantum graphs without back-scattering, Spectral estimates for infinite quantum graphs, Isoperimetry in supercritical bond percolation in dimensions three and higher, Probabilistically checkable proofs and their consequences for approximation algorithms, Strong uniform times and finite random walks, Expanders obtained from affine transformations, Finite fields and Ramanujan graphs, The infection time of graphs, Poisson-Dirichlet distribution for random Belyi surfaces, Expansion properties of Cayley graphs of the alternating groups, Cutoff on all Ramanujan graphs, Semidefinite programming in combinatorial optimization, Explicit construction of linear sized tolerant networks, Isoperimetric inequalities, growth, and the spectrum of graphs, A bipartite analogue of Dilworth's theorem, Ramanujan graphs, The structure of trivalent graphs with minimal eigenvalue gap, 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, New spectral lower bounds on the bisection width of graphs, On embedding expanders into \(\ell_p\) spaces, On the power of two-point based sampling, Old and new results on algebraic connectivity of graphs, Spectra of graphs and fractal dimensions. I, The electrical resistance of a graph captures its commute and cover times, Integral circulant Ramanujan graphs of prime power order, A Cheeger-type inequality on simplicial complexes, Linear programming bounds for regular graphs, Randomized oblivious integral routing for minimizing power cost, Algebraic proof systems over formulas., Expansion in \(\text{SL}_d(\mathbb Z/q\mathbb Z)\), \(q\) arbitrary., Minimizing the least eigenvalue of graphs with fixed order and size, Small-diameter Cayley graphs for finite simple groups, Relative expanders or weakly relatively Ramanujan graphs., Variants of Kazhdan's property for subgroups of semisimple groups, Almost-Ramanujan graphs and prime gaps, 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, Diameter, covering index, covering radius and eigenvalues, Eigenvalues, diameter, and mean distance in graphs, Metric uniformization and spectral bounds for graphs, The spectral gap of dense random regular graphs, Extremal results for odd cycles in sparse pseudorandom graphs, Some properties of graphs constructed from 2-designs, On the second eigenvalue and random walks in random \(d\)-regular graphs, On the second eigenvalue of a graph, Beyond the expanders, The symbiotic relationship of combinatorics and matrix theory, Nonlinear lower bounds on the number of processors of circuits with sublinear separators, 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, A domain monotonicity theorem for graphs and Hamiltonicity, Size biased couplings and the spectral gap for random regular graphs, Lower bounds for the first eigenvalue of certain M-matrices associated with graphs, On sensitivity of mixing times and cutoff, On the multiple threshold decoding of LDPC codes over \(\mathrm{GF}(q)\), Discrepancy minimizing spectral clustering, Chip-firing games on directed graphs, Spectra, Euclidean representations and clusterings of hypergraphs, Laplace eigenvalues of graphs---a survey, Approximating the permanent of graphs with large factors, Testing the expansion of a graph, Simple bounds on the convergence rate of an ergodic Markov chain, Highly symmetric expanders, Probability of graphs with large spectral gap by multicanonical Monte Carlo, Spectra of lifted Ramanujan graphs, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Maximum flows and minimum cuts in the plane, Correlation between graphs with an application to brain network analysis, Evaluating performance of image segmentation criteria and techniques, Some geometric aspects of graphs and their eigenfunctions, A spectral lower bound for the treewidth of a graph and its consequences, Constructing disjoint paths on expander graphs, The second eigenvalue of regular graphs of given girth, On the spectra of certain graphs arising from finite fields, Cryptographic hash functions from expander graphs, Further results on the eccentric distance sum, On a conjecture of Brouwer involving the connectivity of strongly regular graphs, Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?, Censored Glauber dynamics for the mean field Ising model, Lower bounds for the eigenvalues of Laplacian matrices, Chip-firing games on graphs, Laplacian matrices of graphs: A survey, Randomness in interactive proofs, Spectra and optimal partitions of weighted graphs, Relating multiway discrepancy and singular values of nonnegative rectangular matrices, The diameter of the uniform spanning tree of dense graphs, Algebraic and combinatorial expansion in random simplicial complexes, A note on the trace method for random regular graphs, The spectral gap of random regular graphs, A Markovian and Roe-algebraic approach to asymptotic expansion in measure, Near optimal spectral gaps for hyperbolic surfaces, Modularity of minor‐free graphs, Spectrum of Graphs over Rings: A Survey, Generalizing \(p\)-Laplacian: spectral hypergraph theory and a partitioning algorithm, A spectral bound for vertex-transitive graphs and their spanning subgraphs, Order-sensitive domination in partially ordered sets and graphs, Combinatorial Fiedler theory and graph partition, Spectrum of random d‐regular graphs up to the edge, On the eigenvalues of the graphs \(D(5,q)\), Paradigms for Unconditional Pseudorandom Generators, On the second eigenvalue of random bipartite biregular graphs, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs, de Caen's inequality and bounds on the largest Laplacian eigenvalue of a graph, Quasirandomness in hypergraphs, Faster and enhanced inclusion-minimal cograph completion, Generalizing the hypergraph Laplacian via a diffusion process with mediators, Sparse and limited wavelength conversion in all-optical tree networks, Cycle density in infinite Ramanujan graphs, 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, Expansion and Lack Thereof in Randomly Perturbed Graphs

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1112844&oldid=13156471"