Incidence geometry

Last updated

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. [1]

Contents

Incidence structures arise naturally and have been studied in various areas of mathematics. Consequently, there are different terminologies to describe these objects. In graph theory they are called hypergraphs, and in combinatorial design theory they are called block designs. Besides the difference in terminology, each area approaches the subject differently and is interested in questions about these objects relevant to that discipline. Using geometric language, as is done in incidence geometry, shapes the topics and examples that are normally presented. It is, however, possible to translate the results from one discipline into the terminology of another, but this often leads to awkward and convoluted statements that do not appear to be natural outgrowths of the topics. In the examples selected for this article we use only those with a natural geometric flavor.

A special case that has generated much interest deals with finite sets of points in the Euclidean plane and what can be said about the number and types of (straight) lines they determine. Some results of this situation can extend to more general settings since only incidence properties are considered.

Incidence structures

An incidence structure(P, L, I) consists of a set P whose elements are called points, a disjoint set L whose elements are called lines and an incidence relationI between them, that is, a subset of P × L whose elements are called flags. [2] If (A, l) is a flag, we say that A is incident withl or that l is incident with A (the terminology is symmetric), and write A I l. Intuitively, a point and line are in this relation if and only if the point is on the line. Given a point B and a line m which do not form a flag, that is, the point is not on the line, the pair (B, m) is called an anti-flag.

Distance in an incidence structure

There is no natural concept of distance (a metric) in an incidence structure. However, a combinatorial metric does exist in the corresponding incidence graph (Levi graph), namely the length of the shortest path between two vertices in this bipartite graph. The distance between two objects of an incidence structure – two points, two lines or a point and a line – can be defined to be the distance between the corresponding vertices in the incidence graph of the incidence structure.

Another way to define a distance again uses a graph-theoretic notion in a related structure, this time the collinearity graph of the incidence structure. The vertices of the collinearity graph are the points of the incidence structure and two points are joined if there exists a line incident with both points. The distance between two points of the incidence structure can then be defined as their distance in the collinearity graph.

When distance is considered in an incidence structure, it is necessary to mention how it is being defined.

Partial linear spaces

Incidence structures that are most studied are those that satisfy some additional properties (axioms), such as projective planes, affine planes, generalized polygons, partial geometries and near polygons. Very general incidence structures can be obtained by imposing "mild" conditions, such as:

A partial linear space is an incidence structure for which the following axioms are true: [3]

In a partial linear space it is also true that every pair of distinct lines meet in at most one point. This statement does not have to be assumed as it is readily proved from axiom one above.

Further constraints are provided by the regularity conditions:

RLk: Each line is incident with the same number of points. If finite this number is often denoted by k.

RPr: Each point is incident with the same number of lines. If finite this number is often denoted by r.

The second axiom of a partial linear space implies that k > 1. Neither regularity condition implies the other, so it has to be assumed that r > 1.

A finite partial linear space satisfying both regularity conditions with k, r > 1 is called a tactical configuration. [4] Some authors refer to these simply as configurations , [5] or projective configurations. [6] If a tactical configuration has n points and m lines, then, by double counting the flags, the relationship nr = mk is established. A common notation refers to (nr, mk)-configurations. In the special case where n = m (and hence, r = k) the notation (nk, nk) is often simply written as (nk).

Simplest non-trivial linear space Sample Incidence.jpg
Simplest non-trivial linear space

A linear space is a partial linear space such that: [7]

Some authors add a "non-degeneracy" (or "non-triviality") axiom to the definition of a (partial) linear space, such as:

This is used to rule out some very small examples (mainly when the sets P or L have fewer than two elements) that would normally be exceptions to general statements made about the incidence structures. An alternative to adding the axiom is to refer to incidence structures that do not satisfy the axiom as being trivial and those that do as non-trivial.

Each non-trivial linear space contains at least three points and three lines, so the simplest non-trivial linear space that can exist is a triangle.

A linear space having at least three points on every line is a Sylvester–Gallai design.

Fundamental geometric examples

Some of the basic concepts and terminology arises from geometric examples, particularly projective planes and affine planes.

Projective planes

A projective plane is a linear space in which:

and that satisfies the non-degeneracy condition:

There is a bijection between P and L in a projective plane. If P is a finite set, the projective plane is referred to as a finite projective plane. The order of a finite projective plane is n = k – 1, that is, one less than the number of points on a line. All known projective planes have orders that are prime powers. A projective plane of order n is an ((n2 + n + 1)n + 1) configuration.

The smallest projective plane has order two and is known as the Fano plane.

Projective plane of order 2
the Fano plane Fano plane.svg
Projective plane of order 2
the Fano plane

Fano plane

This famous incidence geometry was developed by the Italian mathematician Gino Fano. In his work [9] on proving the independence of the set of axioms for projective n-space that he developed, [10] he produced a finite three-dimensional space with 15 points, 35 lines and 15 planes, in which each line had only three points on it. [11] The planes in this space consisted of seven points and seven lines and are now known as Fano planes.

The Fano plane cannot be represented in the Euclidean plane using only points and straight line segments (i.e., it is not realizable). This is a consequence of the Sylvester–Gallai theorem, according to which every realizable incidence geometry must include an ordinary line, a line containing only two points. The Fano plane has no such line (that is, it is a Sylvester–Gallai configuration), so it is not realizable. [12]

A complete quadrangle consists of four points, no three of which are collinear. In the Fano plane, the three points not on a complete quadrangle are the diagonal points of that quadrangle and are collinear. This contradicts the Fano axiom, often used as an axiom for the Euclidean plane, which states that the three diagonal points of a complete quadrangle are never collinear.

Affine planes

An affine plane is a linear space satisfying:

and satisfying the non-degeneracy condition:

The lines l and m in the statement of Playfair's axiom are said to be parallel. Every affine plane can be uniquely extended to a projective plane. The order of a finite affine plane is k, the number of points on a line. An affine plane of order n is an ((n2)n + 1, (n2 + n)n) configuration.

Affine plane of order 3
(Hesse configuration) Hesse configuration.svg
Affine plane of order 3
(Hesse configuration)

Hesse configuration

The affine plane of order three is a (94, 123) configuration. When embedded in some ambient space it is called the Hesse configuration . It is not realizable in the Euclidean plane but is realizable in the complex projective plane as the nine inflection points of an elliptic curve with the 12 lines incident with triples of these.

The 12 lines can be partitioned into four classes of three lines apiece where, in each class the lines are mutually disjoint. These classes are called parallel classes of lines. Adding four new points, each being added to all the lines of a single parallel class (so all of these lines now intersect), and one new line containing just these four new points produces the projective plane of order three, a (134) configuration. Conversely, starting with the projective plane of order three (it is unique) and removing any single line and all the points on that line produces this affine plane of order three (it is also unique).

Removing one point and the four lines that pass through that point (but not the other points on them) produces the (83) Möbius–Kantor configuration.

Partial geometries

Partial geometry pg(2,2,1) GQ(2,2), the Doily.svg
Partial geometry pg(2,2,1)

Given an integer α ≥ 1, a tactical configuration satisfying:

is called a partial geometry. If there are s + 1 points on a line and t + 1 lines through a point, the notation for a partial geometry is pg(s, t, α).

If α = 1 these partial geometries are generalized quadrangles.

If α = s + 1 these are called Steiner systems.

Generalized polygons

For n > 2, [13] a generalized n-gon is a partial linear space whose incidence graph Γ has the property:

A generalized 2-gon is an incidence structure, which is not a partial linear space, consisting of at least two points and two lines with every point being incident with every line. The incidence graph of a generalized 2-gon is a complete bipartite graph.

A generalized n-gon contains no ordinary m-gon for 2 ≤ m < n and for every pair of objects (two points, two lines or a point and a line) there is an ordinary n-gon that contains them both.

Generalized 3-gons are projective planes. Generalized 4-gons are called generalized quadrangles. By the Feit-Higman theorem the only finite generalized n-gons with at least three points per line and three lines per point have n = 2, 3, 4, 6 or 8.

Near polygons

For a non-negative integer d a near 2d-gon is an incidence structure such that:

A near 0-gon is a point, while a near 2-gon is a line. The collinearity graph of a near 2-gon is a complete graph. A near 4-gon is a generalized quadrangle (possibly degenerate). Every finite generalized polygon except the projective planes is a near polygon. Any connected bipartite graph is a near polygon and any near polygon with precisely two points per line is a connected bipartite graph. Also, all dual polar spaces are near polygons.

Many near polygons are related to finite simple groups like the Mathieu groups and the Janko group J2. Moreover, the generalized 2d-gons, which are related to Groups of Lie type, are special cases of near 2d-gons.

Möbius planes

An abstract Möbius plane (or inversive plane) is an incidence structure where, to avoid possible confusion with the terminology of the classical case, the lines are referred to as cycles or blocks.

Specifically, a Möbius plane is an incidence structure of points and cycles such that:

The incidence structure obtained at any point P of a Möbius plane by taking as points all the points other than P and as lines only those cycles that contain P (with P removed), is an affine plane. This structure is called the residual at P in design theory.

A finite Möbius plane of orderm is a tactical configuration with k = m + 1 points per cycle that is a 3-design, specifically a 3-(m2 + 1, m + 1, 1) block design.

Incidence theorems in the Euclidean plane

The Sylvester-Gallai theorem

A question raised by J.J. Sylvester in 1893 and finally settled by Tibor Gallai concerned incidences of a finite set of points in the Euclidean plane.

Theorem (Sylvester-Gallai): A finite set of points in the Euclidean plane is either collinear or there exists a line incident with exactly two of the points.

A line containing exactly two of the points is called an ordinary line in this context. Sylvester was probably led to the question while pondering about the embeddability of the Hesse configuration.

The de Bruijn–Erdős theorem

A related result is the de Bruijn–Erdős theorem. Nicolaas Govert de Bruijn and Paul Erdős proved the result in the more general setting of projective planes, but it still holds in the Euclidean plane. The theorem is: [14]

In a projective plane, every non-collinear set of n points determines at least n distinct lines.

As the authors pointed out, since their proof was combinatorial, the result holds in a larger setting, in fact in any incidence geometry in which there is a unique line through every pair of distinct points. They also mention that the Euclidean plane version can be proved from the Sylvester-Gallai theorem using induction.

The Szemerédi–Trotter theorem

A bound on the number of flags determined by a finite set of points and the lines they determine is given by:

Theorem (Szemerédi–Trotter): given n points and m lines in the plane, the number of flags (incident point-line pairs) is:

and this bound cannot be improved, except in terms of the implicit constants.

This result can be used to prove Beck's theorem.

A similar bound for the number of incidences is conjectured for point-circle incidences, but only weaker upper bounds are known. [15]

Beck's theorem

Beck's theorem says that finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a single line, and one where a large number of lines are needed to connect all the points.

The theorem asserts the existence of positive constants C, K such that given any n points in the plane, at least one of the following statements is true:

  1. There is a line that contains at least n/C of the points.
  2. There exist at least n2/K lines, each of which contains at least two of the points.

In Beck's original argument, C is 100 and K is an unspecified constant; it is not known what the optimal values of C and K are.

More examples

See also

Notes

  1. As, for example, L. Storme does in his chapter on Finite Geometry in Colbourn & Dinitz (2007 , pg. 702)
  2. Technically this is a rank two incidence structure, where rank refers to the number of types of objects under consideration (here, points and lines). Higher ranked structures are also studied, but several authors limit themselves to the rank two case, and we shall do so here.
  3. Moorhouse , pg.5
  4. Dembowski 1968 , p. 5
  5. Coxeter, H. S. M. (1969), Introduction to Geometry, New York: John Wiley & Sons, p. 233, ISBN   978-0-471-50458-0
  6. Hilbert, David; Cohn-Vossen, Stephan (1952), Geometry and the Imagination (2nd ed.), Chelsea, pp. 94–170, ISBN   978-0-8284-1087-8
  7. Moorhouse , pg. 5
  8. There are several alternatives for this "non-triviality" axiom. This could be replaced by "there exist three points not on the same line" as is done in Batten & Beutelspacher (1993 , pg. 1). There are other choices, but they must always be existence statements that rule out the very simple cases to exclude.
  9. Fano, G. (1892), "Sui postulati fondamentali della geometria proiettiva", Giornale di Matematiche, 30: 106–132
  10. Collino, Conte & Verra 2013 , p. 6
  11. Malkevitch Finite Geometries? an AMS Featured Column
  12. Aigner & Ziegler (2010).
  13. The use of n in the name is standard and should not be confused with the number of points in a configuration.
  14. Weisstein, Eric W., "de Bruijn–Erdős Theorem" from MathWorld
  15. Aronov, Boris; Sharir, Micha (1 November 2002). "Cutting Circles into Pseudo-Segments and Improved Bounds for Incidences% and Complexity of Many Faces". Discrete & Computational Geometry . 28 (4): 475–490. doi: 10.1007/s00454-001-0084-1 .

Related Research Articles

<span class="mw-page-title-main">Projective plane</span> Geometric concept of a 2D space with a "point at infinity" adjoined

In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect. A projective plane can be thought of as an ordinary plane equipped with additional "points at infinity" where parallel lines intersect. Thus any two distinct lines in a projective plane intersect at exactly one point.

<span class="mw-page-title-main">Projective space</span> Completion of the usual space with "points at infinity"

In mathematics, the concept of a projective space originated from the visual effect of perspective, where parallel lines seem to meet at infinity. A projective space may thus be viewed as the extension of a Euclidean space, or, more generally, an affine space with points at infinity, in such a way that there is one point at infinity of each direction of parallel lines.

<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.

<span class="mw-page-title-main">Affine geometry</span> Euclidean geometry without distance and angles

In mathematics, affine geometry is what remains of Euclidean geometry when ignoring the metric notions of distance and angle.

<span class="mw-page-title-main">Finite geometry</span> Geometric system with a finite number of points

A finite geometry is any geometric system that has only a finite number of points. The familiar Euclidean geometry is not finite, because a Euclidean line contains infinitely many points. A geometry based on the graphics displayed on a computer screen, where the pixels are considered to be the points, would be a finite geometry. While there are many systems that could be called finite geometries, attention is mostly paid to the finite projective and affine spaces because of their regularity and simplicity. Other significant types of finite geometry are finite Möbius or inversive planes and Laguerre planes, which are examples of a general type called Benz planes, and their higher-dimensional analogs such as higher finite inversive geometries.

In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the general case situation, as opposed to some more special or coincidental cases that are possible, which is referred to as special position. Its precise meaning differs in different settings.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Fano plane</span> Geometry with 7 points and 7 lines

In finite geometry, the Fano plane is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines cannot exist with this pattern of incidences in Euclidean geometry, but they can be given coordinates using the finite field with two elements. The standard notation for this plane, as a member of a family of projective spaces, is PG(2, 2). Here PG stands for "projective geometry", the first parameter is the geometric dimension and the second parameter is the order.

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>

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 on which lines for all points and lines. What is left is the incidence structure of the Euclidean plane.

<span class="mw-page-title-main">Sylvester–Gallai theorem</span> Existence of a line through two points

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 projective geometry, a homography is an isomorphism of projective spaces, induced by an isomorphism of the vector spaces from which the projective spaces derive. It is a bijection that maps lines to lines, and thus a collineation. In general, some collineations are not homographies, but the fundamental theorem of projective geometry asserts that is not so in the case of real projective spaces of dimension at least two. Synonyms include projectivity, projective transformation, and projective collineation.

<span class="mw-page-title-main">Configuration (geometry)</span> Points and lines with equal incidences

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.

A linear space is a basic structure in incidence geometry. A linear space consists of a set of elements called points, and a set of elements called lines. Each line is a distinct subset of the points. The points in a line are said to be incident with the line. Any two lines may have no more than one point in common. Intuitively, this rule can be visualized as the property that two straight lines never intersect more than once.

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.

Geometric Algebra is a book written by Emil Artin and published by Interscience Publishers, New York, in 1957. It was republished in 1988 in the Wiley Classics series (ISBN 0-471-60839-4).

<span class="mw-page-title-main">Hesse configuration</span> Geometric configuration of 9 points and 12 lines

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 (1844), and is also known as Young's geometry, named after the later work of John Wesley Young on finite geometry.

In geometry, a Sylvester–Gallai configuration consists of a finite subset of the points of a projective space with the property that the line through any two of the points in the subset also passes through at least one other point of the subset.

In mathematics, the classical Möbius plane is the Euclidean plane supplemented by a single point at infinity. It is also called the inversive plane because it is closed under inversion with respect to any generalized circle, and thus a natural setting for planar inversive geometry.

Near polygon

In mathematics, a near polygon is an incidence geometry introduced by Ernest E. Shult and Arthur Yanushka in 1980. Shult and Yanushka showed the connection between the so-called tetrahedrally closed line-systems in Euclidean spaces and a class of point-line geometries which they called near polygons. These structures generalise the notion of generalized polygon as every generalized 2n-gon is a near 2n-gon of a particular kind. Near polygons were extensively studied and connection between them and dual polar spaces was shown in 1980s and early 1990s. Some sporadic simple groups, for example the Hall-Janko group and the Mathieu groups, act as automorphism groups of near polygons.

References