
related topics 
{math, number, function} 
{rate, high, increase} 
{system, computer, user} 
{household, population, female} 
{math, energy, light} 

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of errorcorrecting codes.^{[1]}
Contents
Definitions
There are several different ways to measure the expansion properties of a finite, undirected multigraph G.
Edge expansion
The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G is defined as
where the minimum is over all nonempty sets S of at most n / 2 vertices and is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.^{[2]} It is closely related to the conductance.^{[citation needed]}
Full article ▸


related documents 
Algebraically closed field 
LL parser 
Integer factorization 
Stokes' theorem 
Associative array 
Document Type Definition 
Parameter 
Topology 
Optimization (mathematics) 
Line integral 
Even and odd permutations 
Henri Lebesgue 
Banach space 
Cauchy's integral formula 
Universal quantification 
Morphism 
A* search algorithm 
Yoneda lemma 
Stoneâ€“Weierstrass theorem 
Topological vector space 
Bspline 
Positivedefinite matrix 
Free group 
Haskell (programming language) 
Solvable group 
Finite difference 
Boolean algebra (structure) 
Hypercomplex number 
Minimum spanning tree 
Liouville number 
