Configuration (geometry)

Last updated October 13, 2024

Configurations (4362) (a complete quadrangle, at left) and (6243) (a complete quadrilateral, at right). Complete-quads.svg — Configurations (4₃6₂) (a complete quadrangle, at left) and (6₂4₃) (a complete quadrilateral, at right).

In mathematics, specifically projective geometry, a configuration in the plane consists of a finite set of points, and a finite arrangement of lines, such that each point is incident to the same number of lines and each line is incident to the same number of points.^[1]

Although certain specific configurations had been studied earlier (for instance by Thomas Kirkman in 1849), the formal study of configurations was first introduced by Theodor Reye in 1876, in the second edition of his book Geometrie der Lage, in the context of a discussion of Desargues' theorem. Ernst Steinitz wrote his dissertation on the subject in 1894, and they were popularized by Hilbert and Cohn-Vossen's 1932 book Anschauliche Geometrie, reprinted in English as Hilbert & Cohn-Vossen (1952).

Configurations may be studied either as concrete sets of points and lines in a specific geometry, such as the Euclidean or projective planes (these are said to be realizable in that geometry), or as a type of abstract incidence geometry. In the latter case they are closely related to regular hypergraphs and biregular bipartite graphs, but with some additional restrictions: every two points of the incidence structure can be associated with at most one line, and every two lines can be associated with at most one point. That is, the girth of the corresponding bipartite graph (the Levi graph of the configuration) must be at least six.

Notation

A configuration in the plane is denoted by ( $p γ ℓ π$ ), where $p$ is the number of points, $ℓ$ the number of lines, $γ$ the number of lines per point, and $π$ the number of points per line. These numbers necessarily satisfy the equation

p\gamma =\ell \pi \,

as this product is the number of point-line incidences (flags).

Configurations having the same symbol, say ( $p γ ℓ π$ ), need not be isomorphic as incidence structures. For instance, there exist three different (9₃ 9₃) configurations: the Pappus configuration and two less notable configurations.

In some configurations, $p = ℓ$ and consequently, $γ = π$ . These are called symmetric or balanced configurations^[2] and the notation is often condensed to avoid repetition. For example, (9₃ 9₃) abbreviates to (9₃).

Examples

Notable projective configurations include the following:

(1₁), the simplest possible configuration, consisting of a point incident to a line. Often excluded as being trivial.
(3₂), the triangle. Each of its three sides meets two of its three vertices, and vice versa. More generally any polygon of $n$ sides forms a configuration of type ( $n 2$ )
(4₃ 6₂), the complete quadrangle
(6₂ 4₃), the Pasch configuration, which includes the complete quadrilateral
(7₃), the Fano plane. This configuration exists as an abstract incidence geometry, but cannot be constructed in the Euclidean plane.
(8₃), the Möbius–Kantor configuration. This configuration describes two quadrilaterals that are simultaneously inscribed and circumscribed in each other. It cannot be constructed in Euclidean plane geometry but the equations defining it have nontrivial solutions in complex numbers.
(9₃), the Pappus configuration
(9₄ 12₃), the Hesse configuration of nine inflection points of a cubic curve in the complex projective plane and the twelve lines determined by pairs of these points. This configuration shares with the Fano plane the property that it contains every line through its points; configurations with this property are known as Sylvester–Gallai configurations due to the Sylvester–Gallai theorem that shows that they cannot be given real-number coordinates.^[3]
(10₃), the Desargues configuration
(12₄ 16₃), the Reye configuration
(12₅ 30₂), the Schläfli double six, formed by 12 of the 27 lines on a cubic surface
(15₃), the Cremona–Richmond configuration, formed by the 15 lines complementary to a double six and their 15 tangent planes
(15₄ 20₃), the Cayley–Salmon configuration
(16₆), the Kummer configuration
(21₄), the Grünbaum–Rigby configuration
(27₃), the Gray configuration
(35₄), Danzer's configuration ^[4]
(60₁₅), the Klein configuration

Duality of configurations

The projective dual of a configuration ( $p γ ℓ π$ ) is a ( $ℓ π p γ$ ) configuration in which the roles of "point" and "line" are exchanged. Types of configurations therefore come in dual pairs, except when taking the dual results in an isomorphic configuration. These exceptions are called self-dual configurations and in such cases $p = ℓ$ .^[5]

The number of ( $n 3$ ) configurations

The number of nonisomorphic configurations of type ( $n 3$ ), starting at $n = 7$ , is given by the sequence

1, 1, 3, 10, 31, 229, 2036, 21399, 245342, ... (sequence A001403 in the OEIS )

These numbers count configurations as abstract incidence structures, regardless of realizability.^[6] As Gropp (1997) discusses, nine of the ten (10₃) configurations, and all of the (11₃) and (12₃) configurations, are realizable in the Euclidean plane, but for each $n \geq 16$ there is at least one nonrealizable ( $n 3$ ) configuration. Gropp also points out a long-lasting error in this sequence: an 1895 paper attempted to list all (12₃) configurations, and found 228 of them, but the 229th configuration, the Gropp configuration, was not discovered until 1988.

Constructions of symmetric configurations

There are several techniques for constructing configurations, generally starting from known configurations. Some of the simplest of these techniques construct symmetric ( $p γ$ ) configurations.

Any finite projective plane of order $n$ is an (( $n 2 + n + 1) n + 1)$ configuration. Let $Π$ be a projective plane of order $n$ . Remove from $Π$ a point $P$ and all the lines of $Π$ which pass through $P$ (but not the points which lie on those lines except for $P$ ) and remove a line $ℓ$ not passing through $P$ and all the points that are on line $ℓ$ . The result is a configuration of type (( $n 2 - 1) n)$ . If, in this construction, the line $ℓ$ is chosen to be a line which does pass through $P$ , then the construction results in a configuration of type (( $n 2) n)$ . Since projective planes are known to exist for all orders $n$ which are powers of primes, these constructions provide infinite families of symmetric configurations.

Not all configurations are realizable, for instance, a (43₇) configuration does not exist.^[7] However, Gropp (1990) has provided a construction which shows that for $k \geq 3$ , a ( $p k$ ) configuration exists for all $p \geq 2 ℓ k + 1$ , where $ℓ k$ is the length of an optimal Golomb ruler of order $k$ .

Unconventional configurations

Higher dimensions

The concept of a configuration may be generalized to higher dimensions,^[8] for instance to points and lines or planes in space. In such cases, the restrictions that no two points belong to more than one line may be relaxed, because it is possible for two points to belong to more than one plane.

Notable three-dimensional configurations are the Möbius configuration, consisting of two mutually inscribed tetrahedra, Reye's configuration, consisting of twelve points and twelve planes, with six points per plane and six planes per point, the Gray configuration consisting of a 3×3×3 grid of 27 points and the 27 orthogonal lines through them, and the Schläfli double six, a configuration with 30 points, 12 lines, two lines per point, and five points per line.

Topological configurations

Configuration in the projective plane that is realized by points and pseudolines is called topological configuration.^[2] For instance, it is known that there exists no point-line (19₄) configurations, however, there exists a topological configuration with these parameters.

Configurations of points and circles

Another generalization of the concept of a configuration concerns configurations of points and circles, a notable example being the (8₃ 6₄) Miquel configuration.^[2]

Notes

↑ In the literature, the terms projective configuration( Hilbert & Cohn-Vossen 1952 ) and tactical configuration of type (1,1)( Dembowski 1968 ) are also used to describe configurations as defined here.
1 2 3 Grünbaum 2009.
↑ Kelly 1986.
↑ Grünbaum 2008, Boben, Gévay & Pisanski 2015
↑ Coxeter 1999 , pp. 106–149
↑ Betten, Brinkmann & Pisanski 2000.
↑ This configuration would be a projective plane of order 6 which does not exist by the Bruck–Ryser theorem.
↑ Gévay 2014.

Related Research Articles

<span class="mw-page-title-main">Projective geometry</span> Type of geometry

In mathematics, projective geometry is the study of geometric properties that are invariant with respect to projective transformations. This means that, compared to elementary Euclidean geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts. The basic intuitions are that projective space has more points than Euclidean space, for a given dimension, and that geometric transformations are permitted that transform the extra points to Euclidean points, and vice versa.

In projective geometry, Desargues's theorem, named after Girard Desargues, states:

In projective geometry, duality or plane duality is a formalization of the striking symmetry of the roles played by points and lines in the definitions and theorems of projective planes. There are two approaches to the subject of duality, one through language and the other a more functional approach through special mappings. These are completely equivalent and either treatment has as its starting point the axiomatic version of the geometries under consideration. In the functional approach there is a map between related geometries that is called a duality. Such a map can be constructed in many ways. The concept of plane duality readily extends to space duality and beyond that to duality in any finite-dimensional projective geometry.

In geometry, an affine plane is a system of points and lines that satisfy the following axioms:

<span class="mw-page-title-main">Incidence structure</span> Abstract mathematical system of two types of objects and a relation between them

In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore all the properties of this geometry except for the relation of which points are incident on which lines for all points and lines. What is left is the incidence structure of the Euclidean plane.

The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. From a collection of points and lines in an incidence geometry or a projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for every incidence between a point and a line. They are named for Friedrich Wilhelm Levi, who wrote about them in 1942.

In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An incidence structure is what is obtained when all other concepts are removed and all that remains is the data about which points lie on which lines. Even with this severe limitation, theorems can be proved and interesting facts emerge concerning this structure. Such fundamental results remain valid when additional concepts are added to form a richer geometry. It sometimes happens that authors blur the distinction between a study and the objects of that study, so it is not surprising to find that some authors refer to incidence structures as incidence geometries.

<span class="mw-page-title-main">Complete quadrangle</span> Geometric figure made of 4 points connected by 6 lines

In mathematics, specifically in incidence geometry and especially in projective geometry, a complete quadrangle is a system of geometric objects consisting of any four points in a plane, no three of which are on a common line, and of the six lines connecting the six pairs of points. Dually, a complete quadrilateral is a system of four lines, no three of which pass through the same point, and the six points of intersection of these lines. The complete quadrangle was called a tetrastigm by Lachlan (1893), and the complete quadrilateral was called a tetragram; those terms are occasionally still used.

In geometry, the Desargues configuration is a configuration of ten points and ten lines, with three points per line and three lines per point. It is named after Girard Desargues.

In geometry, the Möbius–Kantor configuration is a configuration consisting of eight points and eight lines, with three points on each line and three lines through each point. It is not possible to draw points and lines having this pattern of incidences in the Euclidean plane, but it is possible in the complex projective plane.

Ordered geometry is a form of geometry featuring the concept of intermediacy but, like projective geometry, omitting the basic notion of measurement. Ordered geometry is a fundamental geometry forming a common framework for affine, Euclidean, absolute, and hyperbolic geometry.

In geometry, the Möbius configuration or Möbius tetrads is a certain configuration in Euclidean space or projective space, consisting of two tetrahedra that are mutually inscribed: each vertex of one tetrahedron lies on a face plane of the other tetrahedron and vice versa. Thus, for the resulting system of eight points and eight planes, each point lies on four planes, and each plane contains four points.

In geometry, the Hesse configuration is a configuration of 9 points and 12 lines with three points per line and four lines through each point. It can be realized in the complex projective plane as the set of inflection points of an elliptic curve, but it has no realization in the Euclidean plane. It was introduced by Colin Maclaurin and studied by Hesse, and is also known as Young's geometry, named after the later work of John Wesley Young on finite geometry.

In geometry, the Reye configuration, introduced by Theodor Reye (1882), is a configuration of 12 points and 16 lines. Each point of the configuration belongs to four lines, and each line contains three points. Therefore, in the notation of configurations, the Reye configuration is written as $124163$ .

In geometry, the Schläfli double six is a configuration of 30 points and 12 lines in three-dimensional Euclidean space, introduced by Ludwig Schläfli in 1858. The lines of the configuration can be partitioned into two subsets of six lines: each line is disjoint from (skew with) the lines in its own subset of six lines, and intersects all but one of the lines in the other subset of six lines. Each of the 12 lines of the configuration contains five intersection points, and each of these 30 intersection points belongs to exactly two lines, one from each subset, so in the notation of configurations the Schläfli double six is written 30₂12₅.

In mathematics, the Cremona–Richmond configuration is a configuration of 15 lines and 15 points, having 3 points on each line and 3 lines through each point, and containing no triangles. It was studied by Cremona and Richmond. It is a generalized quadrangle with parameters (2,2). Its Levi graph is the Tutte–Coxeter graph.

<i>Geometry and the Imagination</i> 1932 book by David Hilbert and Stefan Cohn-Vossen

Geometry and the Imagination is the English translation of the 1932 book Anschauliche Geometrie by David Hilbert and Stefan Cohn-Vossen.

In geometry, the Grünbaum–Rigby configuration is a symmetric configuration consisting of 21 points and 21 lines, with four points on each line and four lines through each point. Originally studied by Felix Klein in the complex projective plane in connection with the Klein quartic, it was first realized in the Euclidean plane by Branko Grünbaum and John F. Rigby.

In mathematics, Danzer's configuration is a self-dual configuration of 35 lines and 35 points, having 4 points on each line and 4 lines through each point. It is named after the German geometer Ludwig Danzer and was popularised by Branko Grünbaum. The Levi graph of the configuration is the Kronecker cover of the odd graph O₄, and is isomorphic to the middle layer graph of the seven-dimensional hypercube graph Q₇. The middle layer graph of an odd-dimensional hypercube graph Q_2n+1(n,n+1) is a subgraph whose vertex set consists of all binary strings of length 2n + 1 that have exactly n or n + 1 entries equal to 1, with an edge between any two vertices for which the corresponding binary strings differ in exactly one bit. Every middle layer graph is Hamiltonian.

References

Berman, Leah W., "Movable (n₄) configurations", The Electronic Journal of Combinatorics, 13 (1): R104.
Betten, A; Brinkmann, G.; Pisanski, T. (2000), "Counting symmetric configurations", Discrete Applied Mathematics, 99 (1–3): 331–338, doi: 10.1016/S0166-218X(99)00143-2 .
Boben, Marko; Gévay, Gábor; Pisanski, T. (2015), "Danzer's configuration revisited", Advances in Geometry , 15 (4): 393–408.
Coxeter, H.S.M. (1999), "Self-dual configurations and regular graphs", The Beauty of Geometry, Dover, ISBN 0-486-40919-8
Dembowski, Peter (1968), Finite geometries , Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Berlin, New York: Springer-Verlag, ISBN 3-540-61786-8, MR 0233275
Gévay, Gábor (2014), "Constructions for large point-line (n_k) configurations", Ars Mathematica Contemporanea , 7: 175-199.
Gropp, Harald (1990), "On the existence and non-existence of configurations n_k", Journal of Combinatorics and Information System Science, 15: 34–48
Gropp, Harald (1997), "Configurations and their realization", Discrete Mathematics , 174 (1–3): 137–151, doi: 10.1016/S0012-365X(96)00327-5 .
Grünbaum, Branko (2006), "Configurations of points and lines", in Davis, Chandler; Ellers, Erich W. (eds.), The Coxeter Legacy: Reflections and Projections, American Mathematical Society, pp. 179–225.
Grünbaum, Branko (2008), "Musing on an example of Danzer's", European Journal of Combinatorics , 29: 1910-1918.
Grünbaum, Branko (2009), Configurations of Points and Lines, Graduate Studies in Mathematics, vol. 103, American Mathematical Society, ISBN 978-0-8218-4308-6 .
Hilbert, David; Cohn-Vossen, Stephan (1952), Geometry and the Imagination (2nd ed.), Chelsea, pp. 94–170, ISBN 0-8284-1087-9 .
Kelly, L. M. (1986), "A resolution of the Sylvester–Gallai problem of J. P. Serre", Discrete and Computational Geometry , 1 (1): 101–104, doi: 10.1007/BF02187687 .
Pisanski, Tomaž; Servatius, Brigitte (2013), Configurations from a Graphical Viewpoint, Springer, ISBN 9780817683641 .

External links

Weisstein, Eric W., "Configuration", MathWorld

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] In the literature, the terms projective configuration( Hilbert & Cohn-Vossen 1952 ) and tactical configuration of type (1,1)( Dembowski 1968 ) are also used to describe configurations as defined here.

[FOOTNOTEGrünbaum2009-2] 1 2 3 Grünbaum 2009.

[FOOTNOTEKelly1986-3] Kelly 1986.

[4] Grünbaum 2008, Boben, Gévay & Pisanski 2015

[5] Coxeter 1999 , pp. 106–149

[FOOTNOTEBettenBrinkmannPisanski2000-6] Betten, Brinkmann & Pisanski 2000.

[7] This configuration would be a projective plane of order 6 which does not exist by the Bruck–Ryser theorem.

[FOOTNOTEGévay2014-8] Gévay 2014.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]