Expander graph

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 error-correcting 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 \partial(S) 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
B-spline
Positive-definite matrix
Free group
Haskell (programming language)
Solvable group
Finite difference
Boolean algebra (structure)
Hypercomplex number
Minimum spanning tree
Liouville number