incidence structure
   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 ...
, 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 In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometry, geometric setting in which two real number, real quantities are required to determine the position (geometry), position of each point (mathematics), ...
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. Incidence structures are most often considered in the geometrical context where they are abstracted from, and hence generalize, planes (such as
affine Affine may describe any of various topics concerned with connections or affinities. It may refer to: * Affine, a Affinity_(law)#Terminology, relative by marriage in law and anthropology * Affine cipher, a special case of the more general substi ...
, projective, and Möbius planes), but the concept is very broad and not limited to geometric settings. Even in a geometric setting, incidence structures are not limited to just points and lines; higher-dimensional objects (planes, solids, -spaces, conics, etc.) can be used. The study of finite structures is sometimes called
finite geometry Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) Finite number may refer to: * A countable number less than infinity, being the cardinality of a finite set – i.e., some natural number In mathematics, th ...
.


Formal definition and terminology

An incidence structure is a triple () where is a set whose elements are called ''points'', is a distinct set whose elements are called ''lines'' and is the incidence relation. The elements of are called flags. If () is in then one may say that point "lies on" line or that the line "passes through" point . A more "symmetric" terminology, to reflect the
symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
nature of this relation, is that " is ''incident'' with " or that " is incident with " and uses the notation synonymously with . In some common situations may be a set of subsets of in which case incidence will be containment ( if and only if is a member of ). Incidence structures of this type are called ''set-theoretic''. This is not always the case, for example, if is a set of vectors and a set of
square In Euclidean geometry, a square is a regular polygon, regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree (angle), degree angles, π/2 radian angles, or right angles). It can also be defined as a rec ...
matrices Matrix most commonly refers to: * The Matrix (franchise), ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within Th ...
, we may define . This example also shows that while the geometric language of points and lines is used, the object types need not be these geometric objects.


Examples

An incidence structure is ''uniform'' if each line is incident with the same number of points. Each of these examples, except the second, is uniform with three points per line.


Graphs

Any
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
(which need not be simple; loops and
multiple edges In graph theory, multiple edges (also called parallel edges or a multi-edge), are, in an undirected graph, two or more edge (graph theory), edges that are incident (graph theory), incident to the same two vertex (graph theory), vertices, or in a ...
are allowed) is a uniform incidence structure with two points per line. For these examples, the vertices of the graph form the point set, the edges of the graph form the line set, and incidence means that a vertex is an endpoint of an edge.


Linear spaces

Incidence structures are seldom studied in their full generality; it is typical to study incidence structures that satisfy some additional axioms. For instance, 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 (geometry), linear space. The notion is equivalent to that of a ...
'' is an incidence structure that satisfies: # Any two distinct points are incident with at most one common line, and # Every line is incident with at least two points. If the first axiom above is replaced by the stronger: #
  • Any two distinct points are incident with exactly one common line,
  • the incidence structure is called a ''
    linear space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called ''vector (mathematics and physics), vectors'', may be Vector addition, added together and Scalar multiplication, mu ...
    ''.


    Nets

    A more specialized example is a ''k''-net. This is an incidence structure in which the lines fall into ''k'' parallel classes, so that two lines in the same parallel class have no common points, but two lines in different classes have exactly one common point, and each point belongs to exactly one line from each parallel class. An example of a ''k''-net is the set of points of an
    affine plane In geometry, an affine plane is a two-dimensional affine space. Examples Typical examples of affine planes are *Euclidean planes, which are affine planes over the real number, reals equipped with a metric (mathematics), metric, the Euclidean dista ...
    together with ''k'' parallel classes of affine lines.


    Dual structure

    If we interchange the role of "points" and "lines" in C = (P, L, I) we obtain the ''dual structure'', C^* = (L, P, I^*) where is the
    converse relation In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent&nb ...
    of . It follows immediately from the definition that: C^ = C This is an abstract version of
    projective duality In geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of ...
    . A structure C that is
    isomorphic 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 ...
    to its dual C^* is called ''self-dual''. The Fano plane above is a self-dual incidence structure.


    Other terminology

    The concept of an incidence structure is very simple and has arisen in several disciplines, each introducing its own vocabulary and specifying the types of questions that are typically asked about these structures. Incidence structures use a geometric terminology, but in graph theoretic terms they are called
    hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
    s and in design theoretic terms they are called
    block design In combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite set, finite Mathematical structure, structures. It is closely relat ...
    s. They are also known as a ''set system'' or
    family of sets In set theory and related branches of mathematics, a collection F of subsets of a given Set (mathematics), set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a famil ...
    in a general context.


    Hypergraphs

    Each
    hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
    or set system can be regarded as an incidence structure in which the
    universal set In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
    plays the role of "points", the corresponding
    family of sets In set theory and related branches of mathematics, a collection F of subsets of a given Set (mathematics), set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a famil ...
    plays the role of "lines" and the incidence relation is
    set membership 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 mo ...
    "∈". Conversely, every incidence structure can be viewed as a hypergraph by identifying the lines with the sets of points that are incident with them.


    Block designs

    A (general) block design is a set together with a family of subsets of (repeated subsets are allowed). Normally a block design is required to satisfy numerical regularity conditions. As an incidence structure, is the set of points and is the set of lines, usually called ''blocks'' in this context (repeated blocks must have distinct names, so is actually a set and not a multiset). If all the subsets in have the same size, the block design is called ''uniform''. If each element of appears in the same number of subsets, the block design is said to be ''regular''. The dual of a uniform design is a regular design and vice versa.


    Example: Fano plane

    Consider the block design/hypergraph given by: P=\left\, L = \left\. This incidence structure is called the
    Fano plane In finite geometry Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) Finite number may refer to: * A countable number less than infinity, being the cardinality of a finite set – i.e., some natural number ...
    . As a block design it is both uniform and regular. In the labeling given, the lines are precisely the subsets of the points that consist of three points whose labels add up to zero using nim addition. Alternatively, each number, when written in
    binary Binary may refer to: Science and technology Mathematics * Binary number A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typical ...
    , can be identified with a non-zero vector of length three over the binary field. Three vectors that generate a subspace form a line; in this case, that is equivalent to their vector sum being the zero vector.


    Representations

    Incidence structures may be represented in many ways. If the sets and are finite these representations can compactly encode all the relevant information concerning the structure.


    Incidence matrix

    The incidence matrix of a (finite) incidence structure is a (0,1) matrix that has its rows indexed by the points and columns indexed by the lines where the ''ij''-th entry is a 1 if and 0 otherwise. An incidence matrix is not uniquely determined since it depends upon the arbitrary ordering of the points and the lines. The non-uniform incidence structure pictured above (example number 2) is given by: An incidence matrix for this structure is: \begin 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 \end which corresponds to the incidence table: If an incidence structure has an incidence matrix , then the dual structure has the transpose matrix T as its incidence matrix (and is defined by that matrix). An incidence structure is self-dual if there exists an ordering of the points and lines so that the incidence matrix constructed with that ordering is a
    symmetric matrix In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally, Because equal matrices have equal dimensions, only square matrices can be symmetric. The entries of a symmetric matrix are symmetric with re ...
    . With the labels as given in example number 1 above and with points ordered and lines ordered , the Fano plane has the incidence matrix: \begin 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \end . Since this is a symmetric matrix, the Fano plane is a self-dual incidence structure.


    Pictorial representations

    An incidence figure (that is, a depiction of an incidence structure), is constructed by representing the points by dots in a plane and having some visual means of joining the dots to correspond to lines. The dots may be placed in any manner, there are no restrictions on distances between points or any relationships between points. In an incidence structure there is no concept of a point being between two other points; the order of points on a line is undefined. Compare this with
    ordered geometry Ordered geometry is a form of geometry featuring the concept of intermediacy (or "betweenness") but, like projective geometry, omitting the basic notion of measurement. Ordered geometry is a fundamental geometry forming a common framework for affin ...
    , which does have a notion of betweenness. The same statements can be made about the depictions of the lines. In particular, lines need not be depicted by "straight line segments" (see examples 1, 3 and 4 above). As with the pictorial representation of
    graphs Graph may refer to: Mathematics *Graph (discrete mathematics) In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a Set (mathematics), set of objects in which some pairs of the objects are in ...
    , the crossing of two "lines" at any place other than a dot has no meaning in terms of the incidence structure; it is only an accident of the representation. These incidence figures may at times resemble graphs, but they aren't graphs unless the incidence structure is a graph.


    Realizability

    Incidence structures can be modelled by points and curves in the
    Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometry, geometric setting in which two real number, real quantities are required to determine the position (geometry), position of each point (mathematics), ...
    with the usual geometric meaning of incidence. Some incidence structures admit representation by points and (straight) lines. Structures that can be are called ''realizable''. If no ambient space is mentioned then the Euclidean plane is assumed. The Fano plane (example 1 above) is not realizable since it needs at least one curve. The Möbius–Kantor configuration (example 4 above) is not realizable in the Euclidean plane, but it is realizable in the
    complex plane In mathematics, the complex plane is the plane (geometry), plane formed by the complex numbers, with a Cartesian coordinate system such that the -axis, called the real axis, is formed by the real numbers, and the -axis, called the imaginary axis, ...
    . On the other hand, examples 2 and 5 above are realizable and the incidence figures given there demonstrate this. Steinitz (1894) has shown that (incidence structures with points and lines, three points per line and three lines through each point) are either realizable or require the use of only one curved line in their representations. The Fano plane is the unique () and the Möbius–Kantor configuration is the unique ().


    Incidence graph (Levi graph)

    Each incidence structure ''C'' corresponds to a
    bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
    called the
    Levi graph In combinatorics, 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 configu ...
    or incidence graph of the structure. As any bipartite graph is two-colorable, the Levi graph can be given a black and white
    vertex coloring In graph theory In mathematics, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph t ...
    , where black vertices correspond to points and white vertices correspond to lines of ''C''. The edges of this graph correspond to the flags (incident point/line pairs) of the incidence structure. The original Levi graph was the incidence graph of the generalized quadrangle of order two (example 3 above), but the term has been extended by H.S.M. Coxeter to refer to an incidence graph of any incidence structure.


    Levi graph examples

    The Levi graph of the
    Fano plane In finite geometry Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) Finite number may refer to: * A countable number less than infinity, being the cardinality of a finite set – i.e., some natural number ...
    is the
    Heawood graph Heawood is a surname. Notable people with the surname include: * Jonathan Heawood, British journalist * Percy John Heawood (1861–1955), British mathematician ** Heawood conjecture ** Heawood graph ** Heawood number See also * Heywood (surname)
    . Since the Heawood graph is
    connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
    and
    vertex-transitive In geometry, a polytope (e.g. a polygon or polyhedron) or a Tessellation, tiling is isogonal or vertex-transitive if all its vertex (geometry), vertices are equivalent under the Symmetry, symmetries of the figure. This implies that each vertex i ...
    , there exists an
    automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of map (mathematics), mapping the object to itself while preserving all of its structure. The Set (m ...
    (such as the one defined by a reflection about the vertical axis in the figure of the Heawood graph) interchanging black and white vertices. This, in turn, implies that the Fano plane is self-dual. The specific representation, on the left, of the Levi graph of the Möbius–Kantor configuration (example 4 above) illustrates that a rotation of about the center (either clockwise or counterclockwise) of the diagram interchanges the blue and red vertices and maps edges to edges. That is to say that there exists a color interchanging automorphism of this graph. Consequently, the incidence structure known as the Möbius–Kantor configuration is self-dual.


    Generalization

    It is possible to generalize the notion of an incidence structure to include more than two types of objects. A structure with types of objects is called an ''incidence structure of rank'' or a ''rank'' ''geometry''. Formally these are defined as tuples with and I \subseteq \bigcup_ P_i \times P_j. The Levi graph for these structures is defined as a multipartite graph with vertices corresponding to each type being colored the same.


    See also

    *
    Incidence (geometry) In geometry, an incidence Relation (mathematics), relation is a heterogeneous relation that captures the idea being expressed when phrases such as "a point ''lies on'' a line" or "a line is ''contained in'' a plane" are used. The most basic incidenc ...
    *
    Incidence geometry 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 (geometry), inc ...
    * Projective configuration *
    Abstract polytope 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 ...


    Notes


    References

    * * * * * G. Eric Moorhouse (2014
    Incidence Geometry
    via John Baez at
    University of California, Riverside The University of California, Riverside (UCR or UC Riverside) is a public land-grant research university in Riverside, California. It is one of the ten campuses of the University of California The University of California (UC) is a pub ...
    *


    Further reading

    * CRC Press (2000). ''Handbook of discrete and combinatorial mathematics'', (Chapter 12.2), * Harold L. Dorwart (1966) ''The Geometry of Incidence'',
    Prentice Hall Prentice Hall was an American major educational publisher owned by Savvas Learning Company. Prentice Hall publishes print and digital content for the 6–12 and higher-education market, and distributes its technical titles through the Safari B ...
    {{Incidence structures Families of sets Combinatorics Finite geometry Incidence geometry