Fact-checked by Grok 2 weeks ago

Incidence structure

An incidence structure is a fundamental concept in combinatorics, defined as a triple D = (P, B, I), where P is a set of points, B is a disjoint set of blocks (or lines), and I \subseteq P \times B is a binary incidence relation specifying which points lie on which blocks.^[1] This framework captures the relational patterns between elements without assuming geometric embedding, making it versatile for abstract modeling.^[2] Incidence structures form the backbone of design theory, a branch of combinatorics concerned with arranging objects into balanced patterns according to specified rules.^[3] 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.^[1] 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 I, whose row and column sums reflect degrees.^[2] Simple incidence structures require distinct blocks to have distinct point sets, ensuring no redundancy.^[1] 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 Fano plane (order 2) with 7 points and 7 lines.^[2] Balanced incomplete block designs (BIBDs) are another class, where every pair of points appears in exactly \lambda blocks of fixed size k, underpinning statistical experiments and coding theory.^[3] Steiner systems, a special case with \lambda = 1 for t-subsets, like the Steiner triple system of order 7, illustrate extremal configurations with minimal overlaps.^[1] Affine geometries, such as AG_2(3) with 9 points and parallel classes of lines, provide resolvable examples where blocks partition the points.^[2] 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.^[2] 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.^[1]

Definition and Terminology

Formal Definition

An incidence structure is formally defined as a triple (P, B, I), where P is a set whose elements are called points, B is a set whose elements are called blocks (or lines), and I \subseteq P \times B is a binary relation known as the incidence relation, which specifies the pairs (p, \beta) \in I indicating that the point p \in P lies on the block \beta \in B.^[4] 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| (number of points) and b = |B| (number of blocks) are of particular interest. The incidence relation I 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 disjoint union P \cup B.^[4] 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), where P is the set of points, B is the set of blocks, and I \subseteq P \times B is the incidence relation, a point p \in P is said to be incident with a block \beta \in B if the ordered pair (p, \beta) belongs to I.^[1] This binary relation captures the fundamental connection between points and blocks, forming the basis for all derived concepts in the structure.^[5] From the incidence relation, several derived sets can be defined. The point set of a block \beta, denoted p(\beta), consists of all points incident with \beta:

p(\beta) = \{ p \in P \mid (p, \beta) \in I \}.

Dually, the block set of a point p, denoted b(p), comprises all blocks incident with p:

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.^[1] A flag is an incident pair (p, \beta) with p \in P, \beta \in B, and (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, \beta) is the induced substructure on the reduced sets p(\beta) \setminus \{p\} and 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.^[5] Associated with these derived sets are cardinality measures that quantify the structure's uniformity or variability. The replication number of a point p, denoted r_p, is the number of blocks incident with p:

r_p = |b(p)|.

Symmetrically, the block size of a block \beta, denoted k_\beta, is the number of points incident with \beta:

k_\beta = |p(\beta)|.

These parameters describe the degree of each point and block in the bipartite incidence graph.^[1]

Fundamental Examples

Graphs

A graph serves as a fundamental example of an incidence structure, where the set of points P corresponds to the vertices V of the graph, the set of blocks B corresponds to the edges E, and the incidence relation I is defined such that a point p \in P is incident with a block \beta \in B if p is an endpoint of the edge \beta.^[6] In the case of an undirected graph, the relation I is symmetric, meaning that if p is incident with \beta, then \beta is incident with p, reflecting the bidirectional nature of edge endpoints.^[6] Consider the complete graph K_3, also known as a triangle, which provides a simple illustration. Here, P = \{1, 2, 3\} and B = \{e_{12}, e_{23}, e_{31}\}, where each block represents an edge connecting two points. The incidence relation I is given explicitly by: $1 incident with e_{12} and e_{31}; $2 incident with e_{12} and e_{23}; $3 incident with e_{23} and e_{31}.^[7] 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 I. For instance, in a directed cycle on three vertices, P = \{1, 2, 3\} and B = \{a_{12}, a_{23}, a_{31}\}, with incidence defined such that a point p is incident with an arc a_{uv} if p = u (the tail) or p = v (the head); however, one may restrict I to tails only for out-incidence or heads only for in-incidence, yielding an asymmetric relation.^[1] In this context, two points are adjacent if they share a common block, meaning there exists an edge connecting them.^[6] The replication number r_p, or the number of blocks incident with a point p, corresponds to the degree of the vertex p in the graph.^[7]

Linear Spaces

A linear space is a special type of incidence structure consisting of a set of points P and a set of lines \mathcal{L} (blocks), where every pair of distinct points is contained in exactly one line, and every line contains at least two points.^[8] This condition ensures that the structure is pairwise balanced with constant \lambda = 1, meaning each unordered pair of points appears in precisely one block.^[9] Unlike more general incidence structures, linear spaces enforce uniqueness for point pairs without requiring uniform block sizes or additional intersection properties.^[8] The defining axioms of a linear space (P, \mathcal{L}) are as follows:

LS1: For any two distinct points p, q \in P, there exists exactly one line \ell \in \mathcal{L} such that p and q are both incident with \ell.
LS2: Every line \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.^[9] Block sizes k_\ell (the number of points on line \ell) may vary across lines, though many examples feature constant size.^[8] A prominent example of a linear space is the affine plane of order n (where n \geq 2), which has v = n^2 points and b = n(n+1) lines, with each line containing exactly k = n points.^[8] In this structure, lines are partitioned into n+1 parallel classes, each containing n disjoint lines that cover all points, ensuring the pairwise uniqueness while allowing non-intersecting lines. For instance, the affine plane over the finite field \mathbb{F}_q (with n = q) realizes these parameters explicitly through vector space constructions.^[8] Another example is the near-pencil on v \geq 3 points, a degenerate linear space with one long line containing v-1 points and v-1 additional lines of size 2, each connecting a fixed external point to one of the points on the long line.^[10] 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.^[10]

Nets

A net of order n and degree r (with r \geq 2) is a linear space (P, B, I) with |P| = n^2 points and b = r n lines, where the lines are partitioned into r parallel classes; parallelism is an equivalence relation (two lines are parallel if they are equal or disjoint), and each parallel class consists of n disjoint lines, each containing n points, that together partition the point set P. Each point is incident with exactly one line from each parallel class, hence with r lines total. This structure satisfies Euclid's parallel postulate: any line parallel to one line in a parallel class is parallel to all others in that class. Nets are equivalent to r-2 mutually orthogonal Latin squares of order n, and their duals are transversal designs.^[11]^[12] The affine plane AG(2,q) over a finite field of order q (with n = q, r = q+1) exemplifies a net, possessing q^2 points and q(q+1) lines arranged in q+1 parallel classes, with each line containing q points and every point incident with q+1 lines.^[13] 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.^[14] Unlike projective planes, where every pair of lines intersects in exactly one point, nets permit parallel lines that do not intersect, enabling diverse geometric configurations while preserving the linear space axioms.^[12]

Dual Structure

In an incidence structure (P, B, I), the dual structure (P^*, B^*, I^*) is obtained by interchanging the roles of points and blocks, where P^* = B, B^* = P, and (b, p) \in I^* if and only if (p, b) \in I.^[15] This operation inverts the incidence relation while preserving the overall relational framework, effectively swapping the primitive elements without altering the underlying incidences.^[16] The dual preserves key incidence counts but exchanges certain parameters: the number of points v = |P| becomes the number of blocks b^* = |B^*| in the dual, and vice versa b = |B| becomes v^* = |P^*|; similarly, the block size k_\beta = |\{p \in P : (p, \beta) \in I\}| for a block \beta \in B corresponds to the replication number r_p^* = |\{\beta^* \in B^* : (\beta^*, p) \in I^*\}| in the dual, and the replication number r_p = |\{\beta \in B : (p, \beta) \in I\}| for a point p \in P becomes the block size k_{\beta^*}^* for the corresponding block \beta^* \in B^*.^[8] 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 = b and k = r.^[17] For a graph viewed as an incidence structure with points as vertices and blocks as edges (each a 2-element subset 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 line graph 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.^[18] Duality plays a central role in geometric incidence structures, facilitating the study of symmetries 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.^[8]

Hypergraphs

A hypergraph 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 symmetry or additional axioms on the relation. This set-theoretic formulation allows hyperedges— the blocks—to connect any number of points, generalizing the pairwise connections of ordinary graphs. Formally, a hypergraph H = (P, B) has point set P and block set B \subseteq \mathcal{P}(P) \setminus \{\emptyset\}, where \mathcal{P}(P) denotes the power set of P, and incidence I = \{ (p, \beta) \mid p \in \beta \in B \}.^[19] 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.^[19] Key variants include uniform hypergraphs, where all blocks have the same cardinality k, denoted k-uniform, meaning each hyperedge contains exactly k points; for k=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 coding theory for uniform cases or network modeling for bipartite ones.^[19] For example, consider the set system with points P = \{1, 2, 3, 4\} and blocks 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.^[19]

Block Designs

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

Representations and Visualizations

Incidence Matrix

An incidence matrix of an incidence structure with point set V of size v and block set B of size b is a v \times b matrix A = (a_{p\beta}) over \{0,1\}, where the rows are indexed by points p \in V, the columns by blocks \beta \in B, and a_{p\beta} = 1 if p is incident with \beta, and $0 otherwise.^[1] The sum of the entries in row p is the degree r_p of point p, equal to the number of blocks containing p; similarly, the sum of entries in column \beta is the degree k_\beta of block \beta, equal to its cardinality.^[1] The total number of $1s in A equals \sum_p r_p = \sum_\beta k_\beta, which yields the parameter relation v \bar{r} = b \bar{k} for regular structures with constant degrees \bar{r} and \bar{k}.^[1] For a balanced incomplete block design (BIBD) with parameters (v, b, r, k, \lambda), where every pair of distinct points lies in exactly \lambda blocks and every block has size k, the matrix A satisfies

A A^T = (r - \lambda) I_v + \lambda J_v,

where I_v is the v \times v identity matrix and J_v is the v \times v all-ones matrix.^[24] This equation encodes the design's balance property algebraically, as the (p, p') entry of A A^T counts the number of blocks containing both p and p', which is \lambda for p \neq p' and r for p = p'.^[24] The transpose A^T is the incidence matrix of the dual incidence structure, obtained by interchanging the roles of points and blocks while preserving the incidence relation.^[8] Such matrices facilitate parameter computation, as in deriving b = v r / k from the total incidence count, and algebraic analysis; for example, in a projective plane of order n, the square incidence matrix A has determinant \det A = \pm (n+1) n^{(n^2 + n)/2}, which is nonzero and thus confirms non-singularity.^[25]

Incidence Graph

The incidence graph of an incidence structure (P, B, I), also known as the Levi graph, is a bipartite graph G with partite sets corresponding to the points P and blocks B, where an edge exists between a point p \in P and a block \beta \in B if and only if (p, \beta) \in I.^[26] This construction, introduced by F. W. Levi in the context of geometric configurations, provides a graph-theoretic representation that captures the incidence relation directly.^[27] In this bipartite graph, the degree of a point vertex p equals r_p, the number of blocks containing p, while the degree of a block vertex \beta equals k_\beta, the number of points in \beta.^[28] 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.^[27] 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.^[29] A simple example arises from viewing the complete graph K_3 (a triangle) as an incidence structure, with its three vertices as points and three edges as blocks; the resulting Levi graph is a 6-cycle, where each vertex has degree 2.^[30] Another illustrative case is the Fano plane, a projective plane of order 2 with 7 points and 7 lines (blocks), each containing 3 points; its Levi graph is a 14-vertex, 3-regular bipartite graph known as the Heawood graph. The Levi graph offers advantages in analyzing incidence structures through graph theory, such as detecting cycles that reveal combinatorial properties like the absence of certain substructures.^[31] If the incidence structure permits multiple incidences between the same point and block, the Levi graph becomes a multigraph with parallel edges; however, standard treatments assume simple graphs where incidences are unique.^[26]

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.^[8] A classic example is the Fano plane, the smallest projective plane of order 2, which consists of 7 points and 7 lines, each containing 3 points. It is often drawn as a circle enclosing a triangle, 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.^[32]^[8] Visual representations face challenges with non-planar structures, where unavoidable line crossings occur, as seen in drawings of the complete graph 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.^[8] For creating precise diagrams, software like TikZ in LaTeX 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 Fano served to introduce incidence axioms visually.^[8]

Extensions and Generalizations

Realizability Conditions

Geometric realizability of an incidence structure refers to the existence of a faithful embedding in the Euclidean plane 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 signatures, such as pairs of polynomials describing the degrees of points and lines, and properties of the associated Levi graph. For instance, a structure with signature (n x^3, n y^3 + y^2 (1 - y)^2) for n \geq 9 admits a geometric realization if its Levi graph lacks cut-edges that isolate non-geometric 3-regular components.^[33] Planar incidence structures are those whose Levi graph—the bipartite graph 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 K_5 or K_{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.^[34] For projective planes, a fundamental class of symmetric incidence structures, realizability over fields is tied to the order n. Projective planes of order n, where each line contains n+1 points and each point lies on n+1 lines, are realizable as the projective plane \mathrm{PG}(2, q) over the finite field \mathbb{F}_q when n = 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.^[35]^[36] Counterexamples to planarity abound among balanced incomplete block designs (BIBDs), which generalize projective planes. The projective plane of order 4, a (21,5,1)-BIBD with 21 points and 21 blocks of size 5, has a Levi graph with 42 vertices and 105 edges. Since this exceeds the bound e \leq 2v - 4 = 80 for planar bipartite graphs with v \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 \geq 4, similarly violate planarity conditions via Euler's formula or forbidden minors.^[37]

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.^[32]^[8] 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 construction 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.^[38] 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 \mathbb{RP}^2, for example, forms an infinite incidence structure with points as 1-dimensional subspaces of \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 compact, 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.^[39] 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.^[40] 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.^[8]

References

[1]
[PDF] Chapter I. Examples and Basic Definitions
May 28, 2022 · Definition 1.1. An incidence structure is a triple D = (V,B,I) where V and B are any two disjoint sets and I is a binary relation between V and ...
[2]
[PDF] A Course in Combinatorics, SECOND EDITION
... combinatorial theory which is known as design theory. The most general object that is studied in this theory is a so-called incidence structure. This is a ...
[3]
Incidence Structures and Steiner Designs
It deals with a crucial problem of combinatorial theory, namely, that of arranging objects into patterns according to specified rules. We give in this chapter a ...
[4]
Introduction
We start with the general notion of an incidence structure. Definition. An incidence structure is an ordered triple (P, B, I) where. P is a set of points,. B ...
[5]
[PDF] Chamber systems and buildings 1 Incidence geometry
Combinatorialists often refer to the two types of varieties in an incidence structure as points and blocks, and (where possible) like to identify a block with ...Missing: replication | Show results with:replication
[6]
[PDF] Graph Theory with Applications - LSE Department of Mathematics
Feb 1, 2013 · A diagram of a graph merely depicts the incidence relation holding between its vertices and edges. We shall, however, often draw a diagram of a ...
[7]
[PDF] Combinatorial and statistical design 1 Combinatorial design
Let (P,B,I) be an incidence structure. The incidence graph or Levi graph of the structure is the bipartite graph with vertex set P∪B, in which p is adjacent to ...
[8]
[PDF] Incidence Geometry - G Eric Moorhouse
In this respect the study of incidence geometry stands alongside group theory, topology and graph theory as a subject area from which a very small set of axioms ...
[9]
[PDF] linear spaces
Define a linear space to be a near–linear space in which any two points are on a line. A linear space is an incidence structure. I = (P,L) such that.
[10]
[PDF] FINITE LINEAR SPACES AND PROJECTIVE PLANES P. ERDOS ...
A linear space in which one line contains all but one of the points (and hence all other lines are of length two) is called a near-pencil. An FLS which is not a.
[11]
[PDF] Combinatorial and statistical design 1 Combinatorial design
(like any incidence structure) be represented by its incidence graph, a bipartite graph with parts X1 and X2. The graph has the properties. • |X1| = |X2| = v ...
[12]
[PDF] More on Regular Linear Spaces - Colorado State University
A linear space is a point line incidence geometry with the property that every pair ... A mesh with v = k2 is known as a net. A dual mesh is obtained as ...
[13]
Nets and their codes | Designs, Codes and Cryptography
A finitek-net of ordern is an incidence structure ofnk lines andn 2 points, with any two lines either meeting once or being parallel, havingk parallel clas.
[14]
Encyclopaedia of Design Theory: Nets
A net of order n and degree r is an incidence structure (whose elements are called points and lines) having the following properties.
[15]
[PDF] Characterization of Projective Incidence Structures, - DTIC
With any incidence structure (P,L,I) is associated its dual incidence structure (L,P,I*) where 1* = ((L,p):(p, t) E iJ. if L is a set o~ subsets of P and (p ...
[16]
incidence structure - PlanetMath
Mar 22, 2013 · Incidence structures are examples of relational structures. As such, we can define substructures and homomorphisms Mathworld ...Missing: formal Dembowski
[17]
[PDF] FINITE PROJECTIVE PLANES An incidence structure π = (P,L) is ...
The dual of π = (P,L) is the incidence structure π d. = (L,P) where the points in π d correspond to lines in π and lines in π d correspond to point in π, and ...
[18]
A Gentle Introduction to Hypergraph Mathematics - HyperNetX
All Hypergraphs Come in Dual Pairs Just like the “primal” hypergraph has a 2-section, so does the dual. This is called the line graph, and it is an important ...
[19]
https://doi.org/10.1007/978-3-319-00080-0
[20]
https://doi.org/10.1111/j.1469-1809.1939.tb02219.x
[21]
The Nonexistence of Certain Finite Projective Planes
The Nonexistence of Certain Finite Projective Planes. Published online by Cambridge University Press: 20 November 2018. R. H. Bruck and. H. J. Ryser.
[22]
An existence theory for pairwise balanced designs I. Composition ...
15. R.M Wilson. An existence theory for pairwise balanced designs. II. The structure of PBD-closed sets and the existence ...Missing: paper | Show results with:paper
[23]
[PDF] Balanced Incomplete Block Designs and Other Combinatorial Objects
Theorem 1.3 For A, the incidence matrix of a given {v, k, λ} design, we have. AAT = (r − λ)I + λJ,. (5) where I is the v × v identity matrix and J is a v × v ...
[24]
[PDF] On Projective Planes - Johan Kåhrström
Let A be the incidence matrix of a projective plane Π of order n. Then AAT = nI+J, where I is the (n2 + n + 1) × (n2 + n + 1) identity matrix ...
[25]
[PDF] Incidence-free sets and edge domination in incidence graphs - arXiv
Nov 25, 2022 · Throughout, we employ a variety of combinatorial, probabilistic and geometric techniques, supplemented with tools from spectral graph theory.
[26]
The 10-cages and derived configurations - ScienceDirect.com
Jan 28, 2004 · An incidence structure is a (vr) configuration if and only if its Levi graph is r-regular and has girth at least 6.
[27]
(PDF) Expansion Properties Of Levi Graphs. - ResearchGate
Aug 5, 2025 · The Levi graph of a balanced incomplete block design is the bi- partite graph whose vertices are the points and blocks of the design, ...
[28]
[PDF] Geometric constructions of small regular graphs with girth 7 - arXiv
Dec 9, 2023 · The incidence graph, also called as the Levi graph, of a point-line incidence structure is a bipartite graph whose bipartition sets correspond ...
[29]
[PDF] EXPANSION PROPERTIES OF LEVI GRAPHS - Combinatorial Press
A point vertex is connected to a block vertex if the point lies in the block. The graph G is called the Levi graph of the block design. See [7]. The Levi ...
[30]
[PDF] Small graphs and hypergraphs of given degree and girth
Jan 2, 2023 · A (Berge) cycle of length ℓ in a hypergraph corresponds to a cycle of length 2ℓ in its Levi graph. the electronic journal of combinatorics 30(1) ...
[31]
[PDF] INCIDENCE GEOMETRY AND BUILDINGS Nesin Mathematics ...
One of the most famous pictures in geometry must be the Fano plane, Figure 2. Figure 2. The Fano plane. It contains 7 points and 7 lines, satisfying the axioms ...
[32]
[PDF] arXiv:1801.10326v2 [math.CO] 24 Apr 2018
Apr 24, 2018 · The lines of size 2 and 4 are highlighted. The dual incidence structure, in which there is exactly one point of degree 2 and one point of ...
[33]
[PDF] A short proof of Kuratowski's graph planarity criterion - TTIC
In 1930, K. Kuratowski published his well-known graph planarity criterion [1]: a graph is planar if and only if it does not contain a subgraph, homeomorphic ...
[34]
None
Summary of each segment:
[35]
[PDF] Affine planes, ternary rings, and examples of non-Desarguesian ...
Namely, an affine plane is said to be non-Desarguesian if it is not defined over a skew-field. Our main goal is to construct examples of non-Desarguesian planes ...Missing: realizable | Show results with:realizable
[36]
[PDF] Segre's theorem on ovals in Desarguesian projective planes
A projective plane is Desarguesian if it is constructed from a three dimensional vector space over a field (or more generally, a division algebra). Equiva-.
[37]
On the fibre product of incidence structures - SpringerLink
It is shown that in the category of incidence structures a fibre product (pull back) always exists. Several applications to Klingenberg incidence structure.
[38]
Innovations in Incidence Geometry - MSP
We recall that an incidence geometry over a set I is a triple (0,∗,τ) where 0 is a set, τ an onto map from 0 to I and ∗ is an incidence relation on 0 such that ...
[39]
New invariants for incidence structures | Designs, Codes and ...
Feb 29, 2012 · To this end, we introduce new invariants for finite simple incidence structures , which admit both an algebraic and a geometric description.<|control11|><|separator|>