graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a branch of mathematics, a Lévy family of graphs is a family of

graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...

''G''_''n'', ''n'' = 1, 2, 3, ..., which possess a certain type of "compactness" or "tangledness". Many naturally occurring families of graphs are Lévy families. Many mathematicians have noted this fact and have expressed surprise that it does not appear to have a ready explanation. Formally, a family of graphs ''G_n'', ''n'' = 1, 2, 3, ..., is a Lévy family if, for any

\varepsilon>0

\lim_\alpha\left(G_n,\varepsilon\right) =0

where :

\alpha(G,\varepsilon) = \max \left\.

Here ''D'' is the

graph diameter In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance or shortest-path d ...

of ''G'', and ''A''_(''n'') is the ''n''- graph neighborhood of ''A''. Note that the maximization ranges over subsets ''A'' of ''G'', subject to ''A'' being over half the size of ''G'' In words, this means that one can take a subset of size at least half of ''G'', and blow it up by only

\epsilon

of the graph diameter, and end up with nearly all the set. Long "stringy" (i.e. not "compact") families of graphs such as the

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

of order ''n'' clearly don't have such a property: one could consider a subset comprising the ''n/2'' neighborhood of a point (midnight to six o'clock, say). The graph has graph diameter ''D'' of about ''n/2''. So the

\epsilon D

-neighborhood of the subset is only of size about ''n/2''. A Levy family would have this neighborhood covering almost all the set. It should be clear that a Levy family must have a very special type of compact structure. *

Hypercube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, e ...

s of order ''n'' are known to be a Lévy family. * If ''S''_''n'' is the graph with points that are elements of the

permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...

of ''n'' elements, with edges joining points that differ by a transposition, then the series ''S''_''i'', ''i=1,2,...'', is a Lévy family.

References

* Bollobás (editor). ''Probabilistic combinatorics and its applications.''

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings ...

, 1991 (p63) {{DEFAULTSORT:Levy Family Of Graphs Graph families