Configuration (original) (raw)

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

The word configuration is sometimes used to describe a finite collection of points p=(p_1,...,p_n) , p_i in R^d , where R^d is a Euclidean space.

The term "configuration" also is used to describe a finite incidence structure (v_r,b_k) with the following properties (Gropp 1992).

1. There are points and lines.

2. There are points on each line and lines through each point.

3. Two different lines intersect each other at most once and two different points are connected by a line at most once.

The conditions

vr=bk

v>=r(k-1)+1

are necessary for the existence of a configuration. For k=3 , these conditions are also sufficient, and for k=4 this is probably also the case (Gropp 1992). The necessary conditions hold, but there is no 22_5 . For k=6 and 7, the above conditions are not sufficient, as illustrated by the affine projective plane of order 6 ( 36_7 , 42_6 ) and the projective plane (43_7,43_7) .

Configurations are among the oldest combinatorial structures, having been defined by T. Reye in 1876. An -regular graph can be regarded as a configuration (v_r,b_2) by associating nodes with the points, and edges with the lines.

A symmetric configuration n_k=(n_k,n_k) consists of lines and points arranged such that lines pass through each point and there are points on each line. All symmetric n_3 configurations are known for n<=18 (Betten et al. 2000). The number of 7_3 , 8_3 , 9_3 , ... configurations are 1, 1, 3, 10, 31, 229, 2036, 21399, 245342, ..., correcting an error of von Sterneck for 12_3 (OEIS A001403; Sterneck 1894, 1895; Wells 1991, p. 72; Colbourn and Dinitz 1996; Gropp 1997; Hilbert and Cohn-Vossen 1999).

FanoPlane

The Fano plane, in which the central point corresponds to the point at infinity, is the unique 7_3 configuration. It is realizable over the Galois field of order 2 GF(2) , but not over the real or rational numbers (Gropp 1997). There are no 7_3 configurations using points all at finite distances (Wells 1986, p. 75).

Moebius-KantorConfiguration

There are no 8_3 configurations using points all at finite distances (Wells 1986, p. 75), but a single configuration exists with a point at infinity (Kantor 1891). This is known as the Möbius-Kantor configuration (Pisanski and Randić 2000).

Configurations9-3

Kantor (1891) showed that there are three 9_3 configurations, of which the Pappus configuration (left figure) is one (Coxeter 1950; Wells 1986, p. 75). The other two consist of embedded equilateral triangles (Wells 1991, pp. 159-160).

DesarguesConfiguration

Kantor (1881) proved that there are exactly 10 configurations 10_3 , of which the Desargues configuration, illustrated above, is one. However, while not explicitly commented upon in paper, Kantor's (10_3)_4 contained a line which consists of two line segments oriented in slightly different directions. Schroeter (1889) subsequently proved that exactly one of these configurations cannot be drawn in the real or rational planes (Gropp 1997).

There are 31 configurations 11_3 (Gropp 1997), as constructed by Martinetti (1887) using recursive construction method, which were subsequently realized in the plane by Daublebsky von Sterneck (1895), though the proof that all are realizable came only with the work of Sturmfels and White (1990). Page and Dorwart (1984) discuss the 31 11_3 configurations (Wells 1991, p. 63).

There are 229 configurations 12_3 , 228 of which had been found by Daublebsky von Sterneck (1895), with the missing one not found until the work of Gropp (1991). One of the 12_3 configurations is sometimes known as the Coxeter configuration, although it is perhaps better to refer it the Nauru configuration based on its Levi graph (which is the Nauru graph). Coordinates for realizations of all 11_3 and 12_3 configurations appeared in an appendix to Crapo et al.(1988).

The Coxeter configuration is a 28_3 configuration whose Levi graph is the Foster graph F_(056)C .

CremonaRichmondConfig

The Cremona-Richmond configuration, illustrated above, is one of the 245342 15_3 configurations.

There is a (2^(d-1))_d configuration known as the Cox configuration.

The following table summarizes the Levi graphs of some names configurations.

Explore with Wolfram|Alpha

References

Betten, A; Brinkmann, G.; and Pisanski, T "Counting Symmetric Configurations v_3 ." Disc. Appl. Math. 99, 331-338, 2000.Bokowski, J. and Sturmfels, B. Computational Synthetic Geometry. Berlin: Springer-Verlag, p. 41, 1988.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 255, 1996.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.Crapo, H.; Havel, T.; Sturmfels, B.; Whiteley, W.; and White, N. "Symbolic Computations in Geometry." IMA Preprint No. 389. University of Minnesota, 1988.Daublebsky von Sterneck, R. "Die Configuration 11_3 ." Monatshefte f. Math. Phys. 5, 325-331, 1894.Daublebsky von Sterneck, R. "Die Configurationen 12_3 ." Monatshefte f. Math. Phys. 6, 223-255, 1895.Gropp, H. "Configurations and the Tutte Conjecture."Ars. Combin. A 29, 171-177, 1990a.Gropp, H. "On the History of Configurations." Conference San Sebastien (Spain). Sept. 1990b.Gropp, H. "Configurations and Steiner systems S(2,4,25) II--Trojan Configurations n_3 ." In Combinatorics '88, Research and Lecture Notes in Mathematics (Ed. A. Barlotti et al. ) Rende, Italy: Mediterranean Press, pp. 425-435, 1991.Gropp, H. "Enumeration of Regular Graphs 100 Years Ago." Discrete Math. 101, 73-85, 1992.Gropp, H. "Non-Symmetric Configurations with Deficiencies 1 and 2." Combinatorics '90. Recent Trends and Applications. Proceedings of the International Conference Held in Gaeta, May 20-27, 1990 (Ed. A. Barlotti, A. Bichera, P. V. Ceccherini, and G. Tallini). Amsterdam, Netherlands: North-Holland, pp. 227-239, 1992.Gropp, H. "Configurations and Their Realization." Discr. Math. 174, 137-151, 1997.Grünbaum, B. Configurations of Points and Lines. Providence, RI: Amer. Math. Soc., 2009.Hilbert, D. and Cohn-Vossen, S. Geometry and the Imagination. New York: Chelsea, 1999.Kantor, S. "Die Configurationen (3,3)_10 ."Sitzungsber. Akad. Wiss. Wien Math.-Natur. Kl, 84, 1291-1314, 1881.Martinetti, V. "Sulle configurazioni piane mu_3 ." Ann. Mat. Pura Appl. 15, 1-26, 1887.Page, W. and Dorwart, H. L. "Numerical Patterns and Geometrical Configurations."Math. Mag. 57, 82-92, 1984.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Schroeter, H. "Üner die Bildungsweise und geometrische Konstruction der Konfigurationen 10_3 .. Nachr. Ges. Wiss. Göttingen, 193-236, 1889.Sloane, N. J. A. Sequence A001403 in "The On-Line Encyclopedia of Integer Sequences."Sturmfels, B. and White, N. "All 11_3 and 12_3 Configurations are Rational." Aeq. Math. 39, 254-260, 1990.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 75, 1986.Wells, D. The Penguin Dictionary of Curious and Interesting Geometry. London: Penguin, pp. 63 and 159-160, 1991.