Incidence Geometry
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, incidence geometry is the study of
incidence structure 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 al ...
s. A geometric structure such as the
Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
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. 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 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 conne ...
they are called
hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
s, and in
combinatorial design theory Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of ''balance'' and/or ''symmetry''. These c ...
they are called
block design In combinatorial mathematics, a block design is an incidence structure consisting of a set together with a family of subsets known as ''blocks'', chosen such that frequency of the elements satisfies certain conditions making the collection of bl ...
s. 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 In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
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'' consists of a set whose elements are called ''points'', a disjoint set whose elements are called ''lines'' and an ''incidence relation'' between them, that is, a subset of whose elements are called ''flags''. If is a flag, we say that is ''incident with'' or that is incident with (the terminology is symmetric), and write . Intuitively, a point and line are in this relation if and only if the point is ''on'' the line. Given a point and a line which do not form a flag, that is, the point is not on the line, the pair is called an ''anti-flag''.


Distance in an incidence structure

There is no natural concept of distance (a
metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathem ...
) in an incidence structure. However, a combinatorial metric does exist in the corresponding incidence graph (Levi graph), namely the length of the shortest
path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desire p ...
between two vertices in this
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
. 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 plane 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 (namely, parallel lines) that do ...
s, affine planes,
generalized polygon In mathematics, a generalized polygon is an incidence structure introduced by Jacques Tits in 1959. Generalized ''n''-gons encompass as special cases projective planes (generalized triangles, ''n'' = 3) and generalized quadrangles (''n'' = 4). Ma ...
s, partial geometries and
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 ...
s. Very general incidence structures can be obtained by imposing "mild" conditions, such as: A
partial linear space A partial linear space (also semilinear or near-linear space) is a basic incidence structure in the field of incidence geometry, that carries slightly less structure than a linear space. The notion is equivalent to that of a linear hypergraph. Defin ...
is an incidence structure for which the following axioms are true: * Every pair of distinct points determines at most one line. * Every line contains at least two distinct points. 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 . RPr: Each point is incident with the same number of lines. If finite this number is often denoted by . The second axiom of a partial linear space implies that . Neither regularity condition implies the other, so it has to be assumed that . A finite partial linear space satisfying both regularity conditions with is called a ''tactical configuration''. Some authors refer to these simply as '' configurations'', or ''projective configurations''. If a tactical configuration has points and lines, then, by double counting the flags, the relationship is established. A common notation refers to -''configurations''. In the special case where (and hence, ) the notation is often simply written as . A ''linear space'' is a partial linear space such that: * Every pair of distinct points determines exactly one line. Some authors add a "non-degeneracy" (or "non-triviality") axiom to the definition of a (partial) linear space, such as: * There exist at least two distinct lines. This is used to rule out some very small examples (mainly when the sets or 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 plane 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 (namely, parallel lines) that do ...
s and affine planes.


Projective planes

A ''projective plane'' is a linear space in which: * Every pair of distinct lines meet in exactly one point, and that satisfies the non-degeneracy condition: * There exist four points, no three of which are
collinear In geometry, collinearity of a set of points is the property of their lying on a single line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, the term has been used for aligned ...
. There is a
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
between and in a projective plane. If is a finite set, the projective plane is referred to as a ''finite'' projective plane. The order of a finite projective plane is , that is, one less than the number of points on a line. All known projective planes have orders that are
prime power In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
s. A projective plane of order is an configuration. The smallest projective plane has order two and is known as the ''Fano plane''.


Fano plane

This famous incidence geometry was developed by the Italian mathematician
Gino Fano Gino Fano (5 January 18718 November 1952) was an Italian mathematician, best known as the founder of finite geometry. He was born to a wealthy Jewish family in Mantua, in Italy and died in Verona, also in Italy. Fano made various contributions ...
. In his work on proving the independence of the set of axioms for projective ''n''-space that he developed, 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. The planes in this space consisted of seven points and seven lines and are now known as
Fano plane In finite geometry, the Fano plane (after Gino Fano) 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 c ...
s. The Fano plane cannot be represented in the
Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
using only points and straight line segments (i.e., it is not realizable). This is a consequence of the
Sylvester–Gallai theorem 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 ...
, 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 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. ...
), so it is not realizable. A
complete quadrangle In mathematics, specifically in incidence geometry and especially in projective geometry, a complete quadrangle is a system of geometric objects consisting of any four Point (geometry), points in a Plane (geometry), plane, no three of which are C ...
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: * For any point and line not incident with it (an anti-flag) there is exactly one line incident with (that is, ), that does not meet (known as
Playfair's axiom In geometry, Playfair's axiom is an axiom that can be used instead of the fifth postulate of Euclid (the parallel postulate): ''In a plane, given a line and a point not on it, at most one line parallel to the given line can be drawn through the ...
), and satisfying the non-degeneracy condition: * There exists a triangle, i.e. three non-collinear points. The lines and 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 , the number of points on a line. An affine plane of order is an configuration.


Hesse configuration

The affine plane of order three is a configuration. When embedded in some ambient space it is called the
Hesse configuration In geometry, the Hesse configuration, introduced by Colin Maclaurin and studied by , 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 ...
. It is not realizable in the Euclidean plane but is realizable in the
complex projective plane In mathematics, the complex projective plane, usually denoted P2(C), is the two-dimensional complex projective space. It is a complex manifold of complex dimension 2, described by three complex coordinates :(Z_1,Z_2,Z_3) \in \mathbf^3,\qquad (Z_1, ...
as the nine
inflection point In differential calculus and differential geometry, an inflection point, point of inflection, flex, or inflection (British English: inflexion) is a point on a smooth plane curve at which the curvature changes sign. In particular, in the case of ...
s of an
elliptic curve In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
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 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
Möbius–Kantor configuration 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 i ...
.


Partial geometries

Given an integer , a tactical configuration satisfying: * For every anti-flag there are flags such that and , is called a ''partial geometry''. If there are points on a line and lines through a point, the notation for a partial geometry is . If these partial geometries are
generalized quadrangle In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles (yet containing many quadrangles). A generalized quadrangle is by definition a polar space of rank two. They are the with ''n'' = 4 ...
s. If these are called
Steiner system 250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line. In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...
s.


Generalized polygons

For , a generalized -gon is a partial linear space whose incidence graph has the property: * The
girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...
of (length of the shortest cycle) is twice the
diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...
of (the largest distance between two vertices, in this case). 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 -gon contains no ordinary -gon for and for every pair of objects (two points, two lines or a point and a line) there is an ordinary -gon that contains them both. Generalized 3-gons are projective planes. Generalized 4-gons are called
generalized quadrangle In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles (yet containing many quadrangles). A generalized quadrangle is by definition a polar space of rank two. They are the with ''n'' = 4 ...
s. By the Feit-Higman theorem the only finite generalized -gons with at least three points per line and three lines per point have = 2, 3, 4, 6 or 8.


Near polygons

For a non-negative integer a near -gon is an incidence structure such that: * The maximum distance (as measured in the collinearity graph) between two points is , and * For every point and line there is a unique point on that is closest to . 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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
. 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 Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked ...
like the
Mathieu group In group theory, a topic in abstract algebra, the Mathieu groups are the five sporadic simple groups ''M''11, ''M''12, ''M''22, ''M''23 and ''M''24 introduced by . They are multiply transitive permutation groups on 11, 12, 22, 23 or 24 obje ...
s and the
Janko group J2 In the area of modern algebra known as group theory, the Janko group ''J2'' or the Hall-Janko group ''HJ'' is a sporadic simple group of order :   2733527 = 604800 : ≈ 6. History and properties ''J2'' is one of the 26 Spora ...
. Moreover, the generalized 2''d''-gons, which are related to
Groups of Lie type In mathematics, specifically in group theory, the phrase ''group of Lie type'' usually refers to finite groups that are closely related to the group of rational points of a reductive linear algebraic group with values in a finite field. The phras ...
, are special cases of near 2''d''-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: * Every triple of distinct points is incident with precisely one cycle. * For any flag and any point not incident with there is a unique cycle with and . (The cycles are said to ''touch'' at .) * Every cycle has at least three points and there exists at least one cycle. The incidence structure obtained at any point of a Möbius plane by taking as points all the points other than and as lines only those cycles that contain (with removed), is an affine plane. This structure is called the ''residual'' at in design theory. A finite Möbius plane of ''order'' is a tactical configuration with points per cycle that is a 3-design, specifically a block design.


Incidence theorems in the Euclidean plane


The Sylvester-Gallai theorem

A question raised by
J.J. Sylvester James Joseph Sylvester (3 September 1814 â€“ 15 March 1897) was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory, and combinatorics. He played a leadership r ...
in 1893 and finally settled by
Tibor Gallai Tibor Gallai (born Tibor Grünwald, 15 July 1912 – 2 January 1992) was a Hungarian mathematician. He worked in combinatorics, especially in graph theory, and was a lifelong friend and collaborator of Paul Erdős. He was a student of Dénes KŠ...
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 In geometry, collinearity of a set of points is the property of their lying on a single line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, the term has been used for aligned ...
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 Nicolaas Govert (Dick) de Bruijn (; 9 July 1918 – 17 February 2012) was a Dutch mathematician, noted for his many contributions in the fields of analysis, number theory, combinatorics and logic.
and
Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
proved the result in the more general setting of projective planes, but it still holds in the Euclidean plane. The theorem is: ::In a
projective plane 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 (namely, parallel lines) that do ...
, every non-collinear set of points determines at least 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 Induction, Inducible or Inductive may refer to: Biology and medicine * Labor induction (birth/pregnancy) * Induction chemotherapy, in medicine * Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
.


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 points and lines in the plane, the number of flags (incident point-line pairs) is: :O \left ( n^ m^ + n + m \right ), 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.


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 such that given any points in the plane, at least one of the following statements is true: # There is a line that contains at least of the points. # There exist at least lines, each of which contains at least two of the points. In Beck's original argument, is 100 and is an unspecified constant; it is not known what the optimal values of and are.


More examples

* Projective geometries *
Moufang polygon In mathematics, Moufang polygons are a generalization by Jacques Tits of the Moufang planes studied by Ruth Moufang, and are irreducible buildings of rank two that admit the action of root groups. In a book on the topic, Tits and Richard Weiss c ...
*
Schläfli double six In geometry, the Schläfli double six is a configuration of 30 points and 12 lines, introduced by . 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 subse ...
*
Reye configuration In geometry, the Reye configuration, introduced by , 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 ...
*
Cremona–Richmond configuration 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 and . It is a generalized quadrangle wit ...
*
Kummer configuration In geometry, the Kummer configuration, named for Ernst Kummer, is a geometric configuration of 16 points and 16 planes such that each point lies on 6 of the planes and each plane contains 6 of the points. Further, every pair of points is incident ...
*
Klein configuration In geometry, the Klein configuration, studied by , is a geometric configuration related to Kummer surface In algebraic geometry, a Kummer quartic surface, first studied by , is an irreducible nodal surface of degree 4 in \mathbb^3 with the ma ...
*
Non-Desarguesian plane In mathematics, a non-Desarguesian plane is a projective plane that does not satisfy Desargues' theorem (named after Girard Desargues), or in other words a plane that is not a Desarguesian plane. The theorem of Desargues is true in all projective s ...
s


See also

*
Combinatorial design Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of ''balance'' and/or ''symmetry''. These co ...
s *
Finite geometry Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked ...
*
Intersection theorem In projective geometry, an intersection theorem or incidence theorem is a statement concerning an incidence structure – consisting of points, lines, and possibly higher-dimensional objects and their incidences – together with a pair of objects ...
*
Levi graph In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we form ...


Notes


References

* * * * * * * * * * * . * . * .


External links

*
''incidence system''
at the
Encyclopedia of Mathematics The ''Encyclopedia of Mathematics'' (also ''EOM'' and formerly ''Encyclopaedia of Mathematics'') is a large reference work in mathematics. Overview The 2002 version contains more than 8,000 entries covering most areas of mathematics at a graduat ...
{{Incidence structures