Isoperimetric Inequalities For Graphs
In graph theory, isoperimetric inequalities are at the heart of the study of expander graphs, which are sparse graphs that have strong connectivity properties. 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.
Isoperimetric inequalities for graphs relate the size of vertex subsets to the size of their boundary, which is usually measured by the number of edges leaving the subset (edge expansion) or by the number of neighbouring vertices (vertex expansion). For a graph and a number, the following are two standard isoperimetric parameters for graphs.
- The edge isoperimetric parameter:
- The vertex isoperimetric parameter:
Here denotes the set of edges leaving and denotes the set of vertices that have a neighbour in . The isoperimetric problem consists of understanding how the parameters and behave for natural families of graphs.
Read more about this topic: Isoperimetric Inequality
Famous quotes containing the word inequalities:
“In many places the road was in that condition called repaired, having just been whittled into the required semicylindrical form with the shovel and scraper, with all the softest inequalities in the middle, like a hog’s back with the bristles up.”
—Henry David Thoreau (1817–1862)