TOPICS

# Erdős Sequence

Let be an arbitrary graph. Then there is a set and a family of subsets , , ... of which can be put in one-to-one correspondence with the vertices of in such a way that edges of occur iff and , where denotes the empty set. This theorem is attributed by Erdős et al. (1966) to Szpilrajn-Marczewski (1945).

A corollary of this theorem is that for every finite simple graph on vertices, there exists a sequence of distinct nonnegative integers that can be put into one-to-one correspondence with the vertices of in such a way that vertices and are joined by an edge iff and are not relatively prime (i.e., if they share a common factor).

Such a sequence may be termed an Erdős sequence, and the graph corresponding a given Erdős sequence an Erdős graph, terms perhaps introduced here for the first time.

For example, the Erdős sequence (2, 3, 5, 6, 10, 15) corresponds to the 2-triangular grid graph, as illustrated above.

The smallest maximum value in an Erdős sequence on a graph with vertices is given by , where denotes a primorial. This value is achieved by star graphs for .

Simple cases include the empty graph , which has the sequence , where is the th prime, and the complete graph , which has the sequence .

The following table summarizes the Erdős sequences of various graphs that the the lexicographically first having smallest possible maximum value. They are also illustrated above.

 graph Erdős sequence empty graph (1, 2) path graph (2, 4) empty graph (1, 2, 3) path graph (2, 3, 6) triangle graph (2, 4, 6) claw graph (2, 3, 5, 30) tetrahedral graph (2, 4, 6, 8) path graph (3, 5, 6, 10) square graph (10, 14, 15, 21) star graph (2, 3, 5, 7, 210) wheel gaph (6, 10, 14, 15, 21)

## See also

Erdős Graph, Intersection Number

## Explore with Wolfram|Alpha

More things to try:

## References

Čulik, K. "Applications of Graph Theory to Mathematical Logic and Linguistics." Proc. Symp. Graph Theory, Smolenice, 13-20, 1963.Erdős, P.; Goodman, A. W.; and Pósa, L. "The Representation of a Graph by Set Intersections." Canad. J. Math. 18, 106-112, 1966.Szpilrajn-Marczewski, E. "Sur deux propriétes des classes dÕensembles." Fund. Math. 33, 303-307, 1945.

## Cite this as:

Weisstein, Eric W. "Erdős Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ErdosSequence.html