Hubbry Logo
Incidence structureIncidence structureMain
Open search
Incidence structure
Community hub
Incidence structure
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Incidence structure
Incidence structure
Incidence structure
View on Wikipedia
from Wikipedia
Examples of incidence structures:
Example 1: points and lines of the Euclidean plane (top)
Example 2: points and circles (middle),
Example 3: finite incidence structure defined by an incidence matrix (bottom)

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.

Incidence structures are most often considered in the geometrical context where they are abstracted from, and hence generalize, planes (such as affine, 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, n-spaces, conics, etc.) can be used. The study of finite structures is sometimes called finite geometry.[1]

Formal definition and terminology

[edit]

An incidence structure is a triple (P, L, I) where P is a set whose elements are called points, L is a distinct set whose elements are called lines and I ⊆ P × L is the incidence relation. The elements of I are called flags. If (p, l) is in I then one may say that point p "lies on" line l or that the line l "passes through" point p. A more "symmetric" terminology, to reflect the symmetric nature of this relation, is that "p is incident with l" or that "l is incident with p" and uses the notation p I l synonymously with (p, l) ∈ I.[2]

In some common situations L may be a set of subsets of P in which case incidence I will be containment (p I l if and only if p is a member of l). Incidence structures of this type are called set-theoretic.[3] This is not always the case, for example, if P is a set of vectors and L a set of square matrices, 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

[edit]
Main article: Incidence geometry
Some examples of incidence structures

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

[edit]
Main article: incidence (graph)

Any graph (which need not be simple; loops and multiple edges 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

[edit]

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 is an incidence structure that satisfies:

  1. Any two distinct points are incident with at most one common line, and
  2. Every line is incident with at least two points.

If the first axiom above is replaced by the stronger:

  2. Any two distinct points are incident with exactly one common line,

the incidence structure is called a linear space.[4][5]

Nets

[edit]

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 together with k parallel classes of affine lines.

Dual structure

[edit]

If we interchange the role of "points" and "lines" in we obtain the dual structure, where I∗ is the converse relation of I. It follows immediately from the definition that:

This is an abstract version of projective duality.[2]

A structure C that is isomorphic to its dual C∗ is called self-dual. The Fano plane above is a self-dual incidence structure.

Other terminology

[edit]

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 hypergraphs and in design theoretic terms they are called block designs. They are also known as a set system or family of sets in a general context.

Hypergraphs

[edit]
Main article: Hypergraph
Seven points are elements of seven lines in the Fano plane

Each hypergraph or set system can be regarded as an incidence structure in which the universal set plays the role of "points", the corresponding family of subsets plays the role of "lines" and the incidence relation is set membership "∈". 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

[edit]
Main article: Block design

A (general) block design is a set X together with a family F of subsets of X (repeated subsets are allowed). Normally a block design is required to satisfy numerical regularity conditions. As an incidence structure, X is the set of points and F is the set of lines, usually called blocks in this context (repeated blocks must have distinct names, so F is actually a set and not a multiset). If all the subsets in F have the same size, the block design is called uniform. If each element of X 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

[edit]

Consider the block design/hypergraph given by:

This incidence structure is called the Fano plane. 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, 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

[edit]

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

Incidence matrix

[edit]
Main article: Incidence matrix

The incidence matrix of a (finite) incidence structure is a (0,1) matrix that has its rows indexed by the points {pi} and columns indexed by the lines {lj} where the ij-th entry is a 1 if pi I lj and 0 otherwise.[a] An incidence matrix is not uniquely determined since it depends upon the arbitrary ordering of the points and the lines.[6]

The non-uniform incidence structure pictured above (example number 2) is given by:

An incidence matrix for this structure is: which corresponds to the incidence table:

I l m n o p q
A 0 0 0 1 1 0
B 0 0 0 0 1 1
C 1 0 0 0 0 0
D 0 0 1 0 0 0
E 1 0 0 0 0 0
P 1 1 1 1 0 1

If an incidence structure C has an incidence matrix M, then the dual structure C∗ has the transpose matrix MT 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.

With the labels as given in example number 1 above and with points ordered A, B, C, D, G, F, E and lines ordered l, p, n, s, r, m, q, the Fano plane has the incidence matrix: Since this is a symmetric matrix, the Fano plane is a self-dual incidence structure.

Pictorial representations

[edit]

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.[6] 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, 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, 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

[edit]

Incidence structures can be modelled by points and curves in the Euclidean plane 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.[7] On the other hand, examples 2 and 5 above are realizable and the incidence figures given there demonstrate this. Steinitz (1894)[8] has shown that n3-configurations (incidence structures with n points and n 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.[9] The Fano plane is the unique (73) and the Möbius–Kantor configuration is the unique (83).

Incidence graph (Levi graph)

[edit]
Heawood graph with labeling

Each incidence structure C corresponds to a bipartite graph called the Levi graph 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, 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),[10] but the term has been extended by H.S.M. Coxeter[11] to refer to an incidence graph of any incidence structure.[12]

Levi graph of the Möbius–Kantor configuration (#4)

Levi graph examples

[edit]

The Levi graph of the Fano plane is the Heawood graph. Since the Heawood graph is connected and vertex-transitive, there exists an automorphism (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 π/4 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

[edit]

It is possible to generalize the notion of an incidence structure to include more than two types of objects. A structure with k types of objects is called an incidence structure of rank k or a rank k geometry.[12] Formally these are defined as k + 1 tuples S = (P1, P2, ..., Pk, I) with Pi ∩ Pj = ∅ and

The Levi graph for these structures is defined as a multipartite graph with vertices corresponding to each type being colored the same.

See also

[edit]

Notes

[edit]

References

[edit]

Bibliography

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Incidence structure

View on Grokipedia
from Grokipedia
An incidence structure is a fundamental concept in combinatorics, defined as a triple D=(P,B,I)D = (P, B, I), where PP is a set of points, BB is a disjoint set of blocks (or lines), and I⊆P×BI \subseteq P \times B is a binary incidence relation specifying which points lie on which blocks. This framework captures the relational patterns between elements without assuming geometric embedding, making it versatile for abstract modeling. Incidence structures form the backbone of , a branch of concerned with arranging objects into balanced patterns according to specified rules. Key properties include the degree of a point (the number of blocks containing it) and the degree of a block (the number of points it contains), often assumed constant in structured designs for regularity. They generalize simpler configurations like graphs—where points are vertices and blocks are edges—and extend to more complex systems via incidence matrices, (0,1)-matrices encoding the relation II, whose row and column sums reflect degrees. Simple incidence structures require distinct blocks to have distinct point sets, ensuring no redundancy. Notable examples include projective planes, finite incidence structures where any two points determine a unique line and any two lines intersect at a unique point, such as the (order 2) with 7 points and 7 lines. Balanced incomplete block designs (BIBDs) are another class, where every pair of points appears in exactly λ\lambda blocks of fixed size kk, underpinning statistical experiments and . Steiner systems, a special case with λ=1\lambda = 1 for tt-subsets, like the Steiner triple system of order 7, illustrate extremal configurations with minimal overlaps. Affine geometries, such as AG2(3)AG_2(3) with 9 points and parallel classes of lines, provide resolvable examples where blocks partition the points. Beyond pure mathematics, incidence structures have applications in error-correcting codes (e.g., deriving self-dual codes from symmetric designs), network analysis (modeling digraphs and spanning trees), and finite geometries for cryptographic protocols. Existence theorems, such as those ensuring 1-designs via Gale-Ryser conditions on degrees, highlight their constructibility, while open problems like the existence of projective planes of non-prime-power order underscore ongoing research.

Definition and Terminology

Formal Definition

An incidence structure is formally defined as a triple (P,B,I)(P, B, I), where PP is a set whose elements are called points, BB is a set whose elements are called blocks (or lines), and I⊆P×BI \subseteq P \times B is a binary relation known as the incidence relation, which specifies the pairs (p,β)∈I(p, \beta) \in I indicating that the point p∈Pp \in P lies on the block β∈B\beta \in B. Unlike axiomatic systems such as projective or affine geometries, which impose specific incidence axioms (e.g., the existence of unique lines through distinct points), an incidence structure requires no such axioms and thus serves as a general framework encompassing a wide variety of combinatorial configurations. This definition applies equally to both finite and infinite cases, with the finite setting often studied in combinatorial contexts where the cardinalities v=∣P∣v = |P| (number of points) and b=∣B∣b = |B| (number of blocks) are of particular interest. The incidence relation II is typically neither reflexive nor transitive, but in many applications—particularly those modeling undirected geometric incidences—the incidence is symmetric in the sense that if a point lies on a block, the block contains the point, though formally the relation is from points to blocks. Alternatively, some definitions use a symmetric relation on the P∪BP \cup B. For the finite case, additional parameters such as the number of blocks containing a given point (replication number) or the number of points in a given block (block size) may be defined, though these vary across structures and are not part of the core definition.

Basic Terminology

In an incidence structure (P,B,I)(P, B, I), where PP is the set of points, BB is the set of blocks, and I⊆P×BI \subseteq P \times B is the incidence relation, a point p∈Pp \in P is said to be incident with a block β∈B\beta \in B if the ordered pair (p,β)(p, \beta) belongs to II. This binary relation captures the fundamental connection between points and blocks, forming the basis for all derived concepts in the structure. From the incidence relation, several derived sets can be defined. The point set of a block β\beta, denoted p(β)p(\beta), consists of all points incident with β\beta: p(β)={p∈P∣(p,β)∈I}.p(\beta) = \{ p \in P \mid (p, \beta) \in I \}. Dually, the block set of a point pp, denoted b(p)b(p), comprises all blocks incident with pp: b(p)={β∈B∣(p,β)∈I}.b(p) = \{ \beta \in B \mid (p, \beta) \in I \}. These sets provide a set-theoretic perspective on the incidences involving a specific point or block. A flag is an incident pair (p,β)(p, \beta) with p∈Pp \in P, β∈B\beta \in B, and (p,β)∈I(p, \beta) \in I; in the context of rank-2 geometries like incidence structures, flags represent the atomic incidences. The residue of a flag (p,β)(p, \beta) is the induced substructure on the reduced sets p(β)∖{p}p(\beta) \setminus \{p\} and b(p)∖{β}b(p) \setminus \{\beta\}, equipped with the incidence relation restricted to these sets. This substructure captures the local configuration surrounding the flag, excluding the flag elements themselves. Associated with these derived sets are cardinality measures that quantify the structure's uniformity or variability. The replication number of a point pp, denoted rpr_p, is the number of blocks incident with pp: rp=∣b(p)∣.r_p = |b(p)|. Symmetrically, the block size of a block β\beta, denoted kβk_\beta, is the number of points incident with β\beta: kβ=∣p(β)∣.k_\beta = |p(\beta)|. These parameters describe the degree of each point and block in the bipartite incidence graph.

Fundamental Examples

Graphs

A graph serves as a fundamental example of an incidence structure, where the set of points PP corresponds to the vertices VV of the graph, the set of blocks BB corresponds to the edges EE, and the incidence relation II is defined such that a point p∈Pp \in P is incident with a block β∈B\beta \in B if pp is an endpoint of the edge β\beta. In the case of an undirected graph, the relation II is symmetric, meaning that if pp is incident with β\beta, then β\beta is incident with pp, reflecting the bidirectional nature of edge endpoints. Consider the complete graph K3K_3, also known as a , which provides a simple illustration. Here, P={1,2,3}P = \{1, 2, 3\} and B={e12,e23,e31}B = \{e_{12}, e_{23}, e_{31}\}, where each block represents an edge connecting two points. The incidence relation II is given explicitly by: 11 incident with e12e_{12} and e31e_{31}; 22 incident with e12e_{12} and e23e_{23}; 33 incident with e23e_{23} and e31e_{31}. This structure captures the connectivity of the graph, where every pair of distinct points is contained in exactly one block. A variant arises with directed graphs, or digraphs, where blocks are arcs representing oriented edges, introducing potential asymmetry in the incidence relation II. For instance, in a directed cycle on three vertices, P={1,2,3}P = \{1, 2, 3\} and B={a12,a23,a31}B = \{a_{12}, a_{23}, a_{31}\}, with incidence defined such that a point pp is incident with an arc auva_{uv} if p=up = u (the ) or p=vp = v (the head); however, one may restrict II to tails only for out-incidence or heads only for in-incidence, yielding an . In this context, two points are adjacent if they share a common block, meaning there exists an edge connecting them. The replication number rpr_p, or the number of blocks incident with a point pp, corresponds to the degree of the vertex pp in the graph.

Linear Spaces

A linear space is a special type of incidence structure consisting of a set of points PP and a set of lines L\mathcal{L} (blocks), where every pair of distinct points is contained in exactly one line, and every line contains at least two points. This condition ensures that the structure is pairwise balanced with constant λ=1\lambda = 1, meaning each of points appears in precisely one block. Unlike more general incidence structures, linear spaces enforce uniqueness for point pairs without requiring uniform block sizes or additional intersection properties. The defining axioms of a linear space (P,L)(P, \mathcal{L}) are as follows:
  • LS1: For any two distinct points p,q∈Pp, q \in P, there exists exactly one line ℓ∈L\ell \in \mathcal{L} such that pp and qq are both incident with ℓ\ell.
  • LS2: Every line ℓ∈L\ell \in \mathcal{L} is incident with at least two points.
These axioms distinguish linear spaces from partial linear spaces, which allow some pairs to be uncovered, and from projective planes, which add further conditions like non-parallelism. Block sizes kℓk_\ell (the number of points on line ℓ\ell) may vary across lines, though many examples feature constant size. A prominent example of a linear space is the affine plane of order nn (where n≥2n \geq 2), which has v=n2v = n^2 points and b=n(n+1)b = n(n+1) lines, with each line containing exactly k=nk = n points. In this structure, lines are partitioned into n+1n+1 parallel classes, each containing nn disjoint lines that cover all points, ensuring the pairwise uniqueness while allowing non-intersecting lines. For instance, the affine plane over the finite field Fq\mathbb{F}_q (with n=qn = q) realizes these parameters explicitly through vector space constructions. Another example is the near-pencil on v≥3v \geq 3 points, a degenerate linear space with one long line containing v−1v-1 points and v−1v-1 additional lines of size 2, each connecting a fixed external point to one of the points on the long line. This configuration satisfies the axioms: pairs on the long line are uniquely covered by it, pairs involving the external point are covered by the corresponding size-2 line, and no other pairs exist, with all lines having at least two points. Near-pencils highlight minimal non-trivial linear spaces and appear in classifications of small designs.

Nets

A net of order nn and degree rr (with r≥2r \geq 2) is a linear space (P,B,I)(P, B, I) with ∣P∣=n2|P| = n^2 points and b=rnb = r n lines, where the lines are partitioned into rr parallel classes; parallelism is an (two lines are parallel if they are equal or disjoint), and each parallel class consists of nn disjoint lines, each containing nn points, that together partition the point set PP. Each point is incident with exactly one line from each parallel class, hence with rr lines total. This structure satisfies Euclid's : any line parallel to one line in a parallel class is parallel to all others in that class. Nets are equivalent to r−2r-2 of order nn, and their duals are transversal designs. The affine plane AG(2,q)AG(2,q) over a of order qq (with n=qn = q, r=q+1r = q+1) exemplifies a , possessing q2q^2 points and q(q+1)q(q+1) lines arranged in q+1q+1 parallel classes, with each line containing qq points and every point incident with q+1q+1 lines. The smallest non-trivial net is the affine plane of order 2, with 4 points and degree 3, though near-pencils are excluded due to lacking the required parallel class structure. Unlike projective planes, where every pair of lines intersects in exactly one point, nets permit that do not intersect, enabling diverse geometric configurations while preserving the linear space axioms.

Dual Structure

In an incidence structure (P,B,I)(P, B, I), the dual structure (P∗,B∗,I∗)(P^*, B^*, I^*) is obtained by interchanging the roles of points and blocks, where P∗=BP^* = B, B∗=PB^* = P, and (b,p)∈I∗(b, p) \in I^* if and only if (p,b)∈I(p, b) \in I. This operation inverts the incidence relation while preserving the overall relational framework, effectively swapping the primitive elements without altering the underlying incidences. The dual preserves key incidence counts but exchanges certain parameters: the number of points v=∣P∣v = |P| becomes the number of blocks b∗=∣B∗∣b^* = |B^*| in the dual, and vice versa b=∣B∣b = |B| becomes v∗=∣P∗∣v^* = |P^*|; similarly, the block size kβ=∣{p∈P:(p,β)∈I}∣k_\beta = |\{p \in P : (p, \beta) \in I\}| for a block β∈B\beta \in B corresponds to the replication number rp∗=∣{β∗∈B∗:(β∗,p)∈I∗}∣r_p^* = |\{\beta^* \in B^* : (\beta^*, p) \in I^*\}| in the dual, and the replication number rp=∣{β∈B:(p,β)∈I}∣r_p = |\{\beta \in B : (p, \beta) \in I\}| for a point p∈Pp \in P becomes the block size kβ∗∗k_{\beta^*}^* for the corresponding block β∗∈B∗\beta^* \in B^*. A structure is self-dual if it is isomorphic to its dual, meaning there exists a bijection between points and blocks that preserves incidence; notable examples include projective planes, where the symmetry ensures v=bv = b and k=rk = r. For a graph viewed as an incidence structure with points as vertices and blocks as edges (each a 2-element of vertices), the dual has points corresponding to the original edges and blocks to the original vertices, with incidence if an original edge is incident to an original vertex. This dual structure relates to the of the original graph, where vertices represent the original edges and adjacency captures shared vertices, thus inverting the point-block roles within the graph's incidence framework. Duality plays a central role in geometric incidence structures, facilitating the study of and inversions; for instance, the dual of an affine plane is not itself an affine plane but retains related incidence properties, such as parallel classes becoming point partitions, which aids in classifying non-symmetric geometries.

Hypergraphs

A is an incidence structure where the blocks consist of arbitrary finite subsets of the point set, and the incidence relation is given by membership in these subsets, without imposing or additional axioms on the relation. This set-theoretic allows hyperedges— the blocks—to connect any number of points, generalizing the pairwise connections of ordinary graphs. Formally, a H=(P,B)H = (P, B) has point set PP and block set B⊆P(P)∖{∅}B \subseteq \mathcal{P}(P) \setminus \{\emptyset\}, where P(P)\mathcal{P}(P) denotes the power set of PP, and incidence I={(p,β)∣p∈β∈B}I = \{ (p, \beta) \mid p \in \beta \in B \}. Hypergraphs often lack the geometric interpretations typical of axiomatized incidence structures, such as projective planes, unless further conditions are imposed; instead, they emphasize combinatorial properties through set inclusion. Every incidence structure can be viewed as a hypergraph by interpreting the incidence relation as defining subsets (blocks containing incident points), though this may introduce multiplicities if the original relation is not a membership function. This perspective positions hypergraphs as a broad generalization, capturing set systems in combinatorics without requiring balanced or symmetric incidences. Key variants include uniform hypergraphs, where all blocks have the same kk, denoted kk-uniform, meaning each hyperedge contains exactly kk points; for k=2k=2, this reduces to a simple graph. Bipartite hypergraphs arise in contexts where the structure admits a 2-coloring of points such that no hyperedge is monochromatic, generalizing bipartite graphs, though 2-uniform bipartite hypergraphs are precisely the bipartite graphs themselves. These variants facilitate specialized applications, such as in for uniform cases or network modeling for bipartite ones. For example, consider the set system with points P={1,2,3,4}P = \{1, 2, 3, 4\} and blocks B={{1,2},{2,3,4},{1,3}}B = \{ \{1,2\}, \{2,3,4\}, \{1,3\} \}; here, the three hyperedges represent arbitrary connections, with incidences defined by containment, such as point 2 belonging to the first two blocks. This structure illustrates the flexibility of hypergraphs, allowing overlapping subsets of varying sizes without further constraints.

Block Designs

A balanced incomplete block design (BIBD) is a special type of incidence structure (V,B)(V, B) consisting of a finite set VV of vv points and a collection BB of bb blocks (subsets of VV), where each block has exactly kk points (1<k<v1 < k < v), each point lies in exactly rr blocks, and every unordered pair of distinct points is contained in exactly λ\lambda blocks (with λ≥1\lambda \geq 1). This uniformity ensures a high degree of balance, making BIBDs useful in statistical experimentation and coding theory. The parameters v,b,r,k,λv, b, r, k, \lambda are not independent; they satisfy the fundamental relations bk=vrbk = vr (counting point-block incidences) and λ(v−1)=r(k−1)\lambda(v-1) = r(k-1) (counting pairs). Existence of a BIBD requires these relations to hold, but additional necessary conditions apply, particularly for symmetric BIBDs where b=vb = v and r=kr = k. The Bruck–Ryser–Chowla states that if a symmetric BIBD with parameters (v,k,λ)(v, k, \lambda) exists, then if vv is even, k−λk - \lambda must be a perfect square, and if vv is odd, the equation x2=(k−λ)y2+(−1)(v−1)/2λz2x^2 = (k - \lambda)y^2 + (-1)^{(v-1)/2} \lambda z^2 must have a nontrivial solution (or equivalently, vv is a sum of two squares when λ=1\lambda = 1). This , originally proved for projective planes and extended to symmetric designs, rules out many parameter sets, such as v=6v = 6 for λ=1\lambda = 1. BIBDs generalize to pairwise balanced designs (PBDs), which are incidence structures (V,B)(V, B) with ∣V∣=v|V| = v where block sizes come from a prescribed set K={k1,…,km}K = \{k_1, \dots, k_m\} (not necessarily constant), but every pair of distinct points appears in exactly λ\lambda blocks (typically λ=1\lambda = 1). PBDs relax the constant block size condition while preserving pairwise balance, allowing broader constructions via composition theorems. A further is the tt-design, or tt-(v, k, \lambda) design, where every tt-subset of points (for t≥2t \geq 2) is contained in exactly λ\lambda blocks of size kk; a BIBD is precisely a 2-design. Higher tt-designs impose stronger balance on larger intersections, with parameters satisfying analogous counting equations like (vt)λ=b(kt)\binom{v}{t} \lambda = b \binom{k}{t}. A classic example of a BIBD is the Fano plane, a (7,3,1)-design with points labeled {1,2,3,4,5,6,7}\{1,2,3,4,5,6,7\} and blocks (lines) {1,2,4}\{1,2,4\}, {2,3,5}\{2,3,5\}, {3,4,6}\{3,4,6\}, {4,5,7}\{4,5,7\}, {1,5,6}\{1,5,6\}, {2,6,7}\{2,6,7\}, {1,3,7}\{1,3,7\}. Here, b=7b=7, r=3r=3, and each pair appears in exactly one block, illustrating the projective plane of order 2. This structure satisfies the parameter relations: 7⋅3=7⋅37 \cdot 3 = 7 \cdot 3 and 1⋅(7−1)=3⋅(3−1)1 \cdot (7-1) = 3 \cdot (3-1).

Representations and Visualizations

Incidence Matrix

An incidence matrix of an incidence structure with point set VV of size vv and block set BB of size bb is a v×bv \times b matrix A=(apβ)A = (a_{p\beta}) over {0,1}\{0,1\}, where the rows are indexed by points p∈Vp \in V, the columns by blocks β∈B\beta \in B, and apβ=1a_{p\beta} = 1 if pp is incident with β\beta, and 00 otherwise. The sum of the entries in row pp is the degree rpr_p of point pp, equal to the number of blocks containing pp; similarly, the sum of entries in column β\beta is the degree kβk_\beta of block β\beta, equal to its cardinality. The total number of 11s in AA equals ∑prp=∑βkβ\sum_p r_p = \sum_\beta k_\beta, which yields the parameter relation vrˉ=bkˉv \bar{r} = b \bar{k} for regular structures with constant degrees rˉ\bar{r} and kˉ\bar{k}. For a balanced incomplete block design (BIBD) with parameters (v,b,r,k,λ)(v, b, r, k, \lambda), where every pair of distinct points lies in exactly λ\lambda blocks and every block has size kk, the matrix AA satisfies AAT=(r−λ)Iv+λJv,A A^T = (r - \lambda) I_v + \lambda J_v, where IvI_v is the v×vv \times v identity matrix and JvJ_v is the v×vv \times v all-ones matrix. This equation encodes the design's balance property algebraically, as the (p,p′)(p, p') entry of AATA A^T counts the number of blocks containing both pp and p′p', which is λ\lambda for p≠p′p \neq p' and rr for p=p′p = p'. The ATA^T is the of the dual incidence structure, obtained by interchanging the roles of points and blocks while preserving the incidence relation. Such matrices facilitate parameter computation, as in deriving b=vr/kb = v r / k from the total incidence count, and ; for example, in a of order nn, the square incidence matrix AA has det⁡A=±(n+1)n(n2+n)/2\det A = \pm (n+1) n^{(n^2 + n)/2}, which is nonzero and thus confirms non-singularity.

Incidence Graph

The incidence graph of an incidence structure (P,B,I)(P, B, I), also known as the graph, is a GG with partite sets corresponding to the points PP and blocks BB, where an edge exists between a point p∈Pp \in P and a block β∈B\beta \in B (p,β)∈I(p, \beta) \in I. This construction, introduced by F. W. in the context of geometric configurations, provides a graph-theoretic representation that captures the incidence relation directly. In this , the degree of a point vertex pp equals rpr_p, the number of blocks containing pp, while the degree of a block vertex β\beta equals kβk_\beta, the number of points in β\beta. The girth of the Levi graph, which is the length of its shortest cycle, is at least 6 in configurations without repeated incidences or certain degeneracies, as shorter cycles (such as 4-cycles) would indicate multiple blocks sharing the same pair of points or analogous violations. For instance, a 4-cycle in the Levi graph corresponds to two points incident with the same two blocks, reflecting structural redundancies in the incidence relation. A simple example arises from viewing the complete graph K3K_3 (a ) as an incidence structure, with its three vertices as points and three edges as blocks; the resulting graph is a 6-cycle, where each vertex has degree 2. Another illustrative case is the , a of order 2 with 7 points and 7 lines (blocks), each containing 3 points; its graph is a 14-vertex, 3-regular known as the Heawood graph. The Levi graph offers advantages in analyzing incidence structures through , such as detecting cycles that reveal combinatorial properties like the absence of certain substructures. If the incidence structure permits multiple incidences between the same point and block, the Levi graph becomes a with parallel edges; however, standard treatments assume simple graphs where incidences are unique.

Pictorial Representations

Incidence structures are commonly visualized by representing points as dots and blocks as lines, curves, or regions that connect the incident points, thereby illustrating the incidence relation geometrically. This method emphasizes the combinatorial connections without implying metric properties such as distances or angles. Labeled diagrams are particularly useful for small structures, where points and blocks are annotated to clarify the incidences, allowing for multiple equivalent drawings that preserve the same relational information. A classic example is the , the smallest of order 2, which consists of 7 points and 7 lines, each containing 3 points. It is often drawn as a circle enclosing a , with diameters connecting the midpoints of the triangle's sides to a central point, highlighting the symmetric incidences. Another representative case is the affine plane of order 3, featuring 9 points arranged in a 3x3 grid and 12 lines (including rows, columns, and parallels in other directions), depicted as a square lattice to show parallel classes and unique lines through pairs of points. Visual representations face challenges with non-planar structures, where unavoidable line crossings occur, as seen in drawings of the K_5 interpreted as an incidence structure with all pairs as blocks, necessitating intersections that obscure clean embeddings. Such limitations arise because the underlying Levi graph, which captures point-block connectivity, may not admit a planar layout. For creating precise diagrams, software like TikZ in facilitates scalable vector graphics of incidence structures, enabling customized placements of points and curved blocks to minimize visual clutter. Historically, sketches of these structures appear in early geometry texts, such as those axiomatizing projective spaces, where hand-drawn figures of planes like the served to introduce incidence axioms visually.

Extensions and Generalizations

Realizability Conditions

Geometric realizability of an incidence structure refers to the existence of a faithful in the where points are represented as distinct points and blocks as straight lines, preserving the incidence relation. A point-line incidence structure is deemed geometric if such a representation is possible using the standard Euclidean incidence between points and lines. Conditions for realizability often involve combinatorial , such as pairs of polynomials describing the degrees of points and lines, and properties of the associated graph. For instance, a structure with signature (nx3,ny3+y2(1−y)2)(n x^3, n y^3 + y^2 (1 - y)^2) for n≥9n \geq 9 admits a geometric realization if its graph lacks cut-edges that isolate non-geometric 3-regular components. Planar incidence structures are those whose Levi graph—the with points and blocks as partite sets and incidences as edges—is planar, allowing a drawing of the structure in the plane without edge crossings. By Kuratowski's theorem, the Levi graph is planar if and only if it contains no subdivision of K5K_5 or K3,3K_{3,3} as a subgraph. This planarity ensures that points and blocks can be visualized without intersections except at incidences, facilitating straight-line embeddings for simple cases. For projective planes, a fundamental class of symmetric incidence structures, realizability over fields is tied to the order nn. Projective planes of order nn, where each line contains n+1n+1 points and each point lies on n+1n+1 lines, are realizable as the projective plane PG(2,q)\mathrm{PG}(2, q) over the finite field Fq\mathbb{F}_q when n=qn = q is a prime power; these are Desarguesian and admit coordinate systems from the field. Non-Desarguesian projective planes, which fail Desargues' theorem, cannot be coordinatized by fields and thus lack such algebraic realizations; for example, the smallest non-Desarguesian planes of order 9, constructed via alternative division rings, do not embed as subspaces of higher-dimensional projective spaces over commutative fields. Counterexamples to planarity abound among balanced incomplete block designs (BIBDs), which generalize s. The projective plane of order 4, a (21,5,1)-BIBD with 21 points and 21 blocks of size 5, has a graph with 42 vertices and 105 edges. Since this exceeds the bound e≤2v−4=80e \leq 2v - 4 = 80 for planar bipartite graphs with v≥3v \geq 3, the graph is non-planar, implying no crossing-free straight-line drawing exists. Larger BIBDs, such as those from projective planes of order q≥4q \geq 4, similarly violate planarity conditions via or forbidden minors.

Broader Generalizations

Incidence structures generalize to higher ranks by incorporating multiple types of elements beyond points and blocks, such as lines, planes, and higher-dimensional subspaces, with incidence relations defined between consecutive ranks. A rank-n incidence structure consists of n+1 sets of elements, denoted as types, along with a collection of flags specifying incidences between elements of adjacent types, forming a partial order or chamber system that captures multi-dimensional geometric configurations. For instance, projective spaces of dimension greater than 2, like the 3-dimensional projective space over a field, serve as rank-4 structures where points (rank 1), lines (rank 2), planes (rank 3), and the whole space (rank 4) are interrelated via containment. These higher-rank generalizations extend classical geometries, enabling the study of partial geometries, which are rank-2 structures with additional constraints on non-incident elements, but adapted to multi-type settings for broader applications in combinatorial geometry. A categorical perspective on incidence structures treats them as objects in a category where morphisms preserve the incidence relation, mapping points to points and blocks (or higher-type elements) to blocks while maintaining the specified incidences. In this category, denoted IStr, compositions and identities are defined componentwise, and it is isomorphic to the category of set-system hypergraphs under weak homomorphisms that respect subset incidences. Notably, fibre products always exist in this category, allowing the of new structures as pullbacks, which has applications in combining incidence geometries like Klingenberg structures. This framework facilitates the study of functors between categories of incidence structures and related objects, such as quivers or graphs, providing algebraic tools to analyze embeddings and transformations. Incidence structures extend to infinite settings when point sets or block sets are infinite, requiring adaptations to handle unbounded incidences while preserving axioms like unique lines through pairs of points. The real projective plane RP2\mathbb{RP}^2, for example, forms an infinite incidence structure with points as 1-dimensional subspaces of R3\mathbb{R}^3 and lines as 2-dimensional subspaces, where incidence occurs when a point is contained in a line; this structure satisfies projective plane axioms and is topologically , ensuring closed and bounded subsets behave finitely in coverings. Compactness conditions in such infinite geometries often impose topological restrictions, such as the space being a compact manifold, to guarantee properties like finite intersection theorems or the existence of finite substructures approximating the whole. These infinite cases contrast with finite designs by allowing continuous parameters but maintain discrete incidence for algebraic study. In coding theory, incidence structures, particularly block designs, yield linear codes via their incidence matrices over finite fields, where the codewords are spans of block characteristic vectors, and parameters like minimum distance relate to design constants such as block size and intersection numbers. For a t-(v,k,λ) design, the dual code's dimension and strength provide invariants measuring error-correcting capabilities, with the p-rank of the incidence matrix bounding code performance; such codes are used in applications like error detection in communication systems. In database theory, incidence structures model binary relations as bipartite setups, where points and blocks represent entity sets and the incidence indicates associations, facilitating queries on relational data; higher-arity relations can be decomposed into binary incidence structures for embedding into vector spaces or graph databases.

References

  1. https://faculty.etsu.edu/gardnerr/Design-Theory/notes-Design-Theory-grad-BJL/Design-Theory-grad-BJL-1-1.pdf
  2. https://sites.math.rutgers.edu/~zeilberg/akherim/VanlintWilson.pdf
  3. https://link.springer.com/content/pdf/10.1007/978-3-0346-0002-6_1.pdf
  4. https://www.ams.org/bookstore/pspdf/stml-67-prev.pdf
  5. https://webspace.maths.qmul.ac.uk/l.h.soicher/designtheory.org/library/encyc/topics/chabu.pdf
  6. http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf
  7. https://webspace.maths.qmul.ac.uk/l.h.soicher/designtheory.org/library/encyc/topics/des.pdf
  8. http://ericmoorhouse.org/handouts/Incidence_Geometry.pdf
  9. https://people.smp.uq.edu.au/DianeDonovan/teaching/MATH3301/geom-slides2.pdf
  10. https://users.renyi.hu/~p_erdos/1983-05.pdf
  11. https://webspace.maths.qmul.ac.uk/l.h.soicher/designtheory.org/library/encyc/nets/g/
  12. https://link.springer.com/article/10.1007/BF01418529
  13. https://webspace.maths.qmul.ac.uk/p.j.cameron/design/encyc/topics/des.pdf
  14. https://www.math.colostate.edu/~betten/pub/betten31.pdf
  15. https://apps.dtic.mil/sti/tr/pdf/ADA042418.pdf
  16. https://planetmath.org/incidencestructure
  17. https://people.smp.uq.edu.au/DianeDonovan/teaching/MATH3301/geom-slides3.pdf
  18. https://hypernetx.readthedocs.io/en/latest/hypergraph101.html
  19. https://doi.org/10.1007/978-3-319-00080-0
  20. https://doi.org/10.1111/j.1469-1809.1939.tb02219.x
  21. https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/nonexistence-of-certain-finite-projective-planes/2A2E0D91C8E872232A01C7519F14D705
  22. https://www.isibang.ac.in/~sury/parvathy.pdf
  23. https://www.sciencedirect.com/science/article/pii/0097316572900283
  24. https://static.renyi.hu/~dezso/coa/bibdpaper.pdf
  25. http://kahrstrom.com/mathematics/documents/OnProjectivePlanes.pdf
  26. https://arxiv.org/pdf/2211.14339
  27. https://www.sciencedirect.com/science/article/pii/S0012365X03001109
  28. https://www.researchgate.net/publication/220620901_Expansion_Properties_Of_Levi_Graphs
  29. https://arxiv.org/pdf/2312.05620
  30. https://combinatorialpress.com/article/ars/Volume%2520080/volume-80-paper-1.pdf
  31. https://www.combinatorics.org/ojs/index.php/eljc/article/download/v30i1p57/pdf/
  32. https://osebje.famnit.upr.si/~michel.lavrauw/inc_geom_buildings_notes.pdf
  33. https://arxiv.org/pdf/1801.10326
  34. https://home.ttic.edu/~yury/papers/kuratowski.pdf
  35. https://www.ams.org/journals/tran/1943-054-02/S0002-9947-1943-0008892-4/S0002-9947-1943-0008892-4.pdf
  36. https://arxiv.org/pdf/1604.04945
  37. https://www.irishmathsoc.org/bull91/wef/Articles/OCathain/OCathain-wef.pdf
  38. https://link.springer.com/article/10.1007/BF01222854
  39. https://msp.org/iig/2019/17-3/iig-v17-n3-s.pdf
  40. https://link.springer.com/article/10.1007/s10623-012-9636-z
Add your contribution
Related Hubs
User Avatar
No comments yet.