Incidence structure

In mathematics , in particular geometry , the incidence structure denotes a structure that is given by a set of points and a set of blocks disjoint to them, as well as an incidence relation established between these sets . From the set of all possible pairs of points and blocks, the incidence relation only specifies those that designate an incidence of a point with a block (e.g. a line). Due to the general wording, numerous structures can be described as special cases of an incidence structure.

Illustration of incidence structures:
Example 1: The straight lines are different blocks - the incidence reads “Point lies on the straight line”.
Example 2: As example 1, with circles instead of straight lines.
Example 3: Incidence matrix : rows and columns denote points and blocks, the numerical value describes an incidence.
Detailed description of the examples in the text next to it.

definition

An incidence structure is a triple of sets with ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$

${\displaystyle {\mathfrak {p}}\cap {\mathfrak {B}}=\emptyset {\;}}$ and ${\displaystyle {\;}I\subseteq {\mathfrak {p}}\times {\mathfrak {B}}.}$

The elements of hot points , those of blocks . The elements of are called incidences or flags . For one writes and says that the point incurs with the block . ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle I}$ ${\displaystyle (p,B)\in I}$ ${\displaystyle p{\mathrel {\ I\ }}B}$ ${\displaystyle p}$ ${\displaystyle B}$

Examples

• 1) be the set of points in the Euclidean plane and the set of straight lines . The incidence relation indicates whether a point is incising with a straight line , which means here: " lies on ". The symbol means the set of all possible point-block pairs . Since not every point lies on every straight line, the set of incident point-line pairs is a subset of the possible pairs, or . In this case the incidence structure is the real affine plane . ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle I}$ ${\displaystyle p}$ ${\displaystyle G}$ ${\displaystyle p}$ ${\displaystyle G}$ ${\displaystyle {\mathfrak {p}}\times {\mathfrak {B}}}$ ${\displaystyle (p,G)}$ ${\displaystyle I}$ ${\displaystyle I\subseteq {\mathfrak {p}}\times {\mathfrak {B}}}$
• 2) again be the set of points in the Euclidean plane, but is now the set of circles . The incidence here again means “ point is on block ”. ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {B}}}$

In Examples 1 and 2, the underlying sets of points, blocks, and incidences are infinite . In the first example, a block is clearly defined by two points, in the second by three (non- collinear ) points. This results in different properties of the incidence structures.

• 3) be the set of corner points of a square and the set of straight lines through two of these points. Then is a 12-element subset of . In the case of finite examples, the incidence can be described by a matrix in which 1 means that there is an incidence between the respective elements of the row and column, and 0 if there is no incidence. In this case the incidence structure is the minimal model of an affine plane . ${\displaystyle {\mathfrak {p}}=\{a,b,c,d\}}$ ${\displaystyle {\mathfrak {B}}={A,B,C,D,E,F}}$ ${\displaystyle I=\{(a,A),...\}}$ ${\displaystyle {\mathfrak {p}}\times {\mathfrak {B}}}$

In Examples 1, 2 and 3, a block can be understood as the set of points which it incurs. The incidence relation is then the abstinence relation . In the following example this is not possible because a point of the incidence structure is a subspace . In this case, however, the incidence relation can be understood as a subset relation . ${\displaystyle I}$ ${\displaystyle \in }$ ${\displaystyle \subseteq }$

• 4) be the set of straight lines through the origin in Euclidean space, the set of planes of origin . A point inzidiere with a block , if in is contained. The incidence structure in this case is a projective level . ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle p}$ ${\displaystyle G}$ ${\displaystyle p}$ ${\displaystyle G}$
• 5) be the set of points on the unit sphere in 3-dimensional Euclidean space, the set of circles on the unit sphere and the incidence relation. The incidence structure in this case is the real Möbius plane . ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle \in }$ ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},\in )}$

A duality principle applies to important classes of incidence structures . The finite incidence structures are objects of study in finite geometry and thus also in combinatorics . You can assign a finite set of parameters , e.g. B. specify how many blocks two different points intersect with on average; a finite incidence structure, in which such a parameter indicates not only the average value but in each case the actual number of incidences, fulfills a regularity condition . Non-degenerate incidence structures that meet such regularity conditions can be typified by them.

Basic terms and definitions for incidence structures

Isomorphisms of incidence structures

Be and incidence structures. A bijective mapping is called isomorphism of on if: ${\displaystyle {\mathcal {I}}_{1}=({\mathfrak {p_{1}}},{\mathfrak {B_{1}}},I_{1})}$ ${\displaystyle {\mathcal {I}}_{2}=({\mathfrak {p_{2}}},{\mathfrak {B_{2}}},I_{2})}$ ${\displaystyle f\colon \;{\mathfrak {p_{1}}}\cup {\mathfrak {B_{1}}}\rightarrow {\mathfrak {p_{2}}}\cup {\mathfrak {B_{2}}}}$ ${\displaystyle {\mathcal {I}}_{1}}$ ${\displaystyle {\mathcal {I}}_{2}}$

1. ${\displaystyle f}$ maps points to points and blocks to blocks and
2. for all points and blocks of : ${\displaystyle p}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {I}}_{1}}$ ${\displaystyle p{\mathrel {\ I_{1}\ }}B\Leftrightarrow f(p){\mathrel {\ I_{2}\ }}f(B).}$

Simple incidence structure

The incidence structure is called simply if the following applies to any blocks : ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ ${\displaystyle B,C\in {\mathfrak {B}}}$

${\displaystyle \left(\forall p\in {\mathfrak {p}}\colon \;p{\mathrel {\ I\ }}B\Leftrightarrow p{\mathrel {\ I\ }}C\right)\Rightarrow B=C,}$

if all blocks are completely determined by the points which they incline. Equivalent to this is: is simple if and only if is isomorphic to an incidence structure , where is a subset of the power set of . ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}=({\mathfrak {p}}',{\mathfrak {B}}',\in )}$ ${\displaystyle {\mathfrak {B}}'}$ ${\displaystyle {\mathcal {P}}({\mathfrak {p}}')}$ ${\displaystyle {\mathfrak {p}}'}$

duality

• For an incidence structure , the dual incidence structure is formed as follows: ${\displaystyle {\mathcal {I}}=\left({\mathfrak {p}},{\mathfrak {B}},I\right)}$ ${\displaystyle {\mathcal {I}}^{D}=\left({\mathfrak {p}}^{D},{\mathfrak {B}}^{D},I^{D}\right)}$

${\displaystyle {\mathfrak {p}}^{D}={\mathfrak {B}},\quad {\mathfrak {B}}^{D}={\mathfrak {p}},\quad I^{D}=I^{-1}=\left\{(B,p)\mid (p,B)\in I\right\}.}$

So the dual incidence structure arises from letting the blocks play the role of the dots and vice versa. Of course it is ${\displaystyle {\mathcal {I}}^{D}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \left({\mathcal {I}}^{D}\right)^{D}={\mathcal {I}}.}$

• If you swap the words “point” and “block” in a statement A about incidence structures, you get the statement A dual statement .

• For a class of incidence structures, the class of the dual incidence structures is designated. ${\displaystyle K}$ ${\displaystyle K^{D}}$

• A concrete incidence structure is called dual to itself if there is an isomorphism . In other words: is dual to itself if and only if the duality principle applies to the class of structures that are too isomorphic. ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \phi \colon \;{\mathcal {I}}\rightarrow {\mathcal {I}}^{D}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \operatorname {\mathbf {ISO} } ({\mathcal {I}})}$ ${\displaystyle {\mathcal {I}}}$

Notation and basic terms

• An incidence structure is called finite if its point set and its block set are finite.
• An incidence structure is called degenerate if it contains a block for which there are no two points that do not incise with this block, otherwise the structure is called non-degenerate . An incidence structure is not degenerate if and only if there are at least two different points for each block that do not incur with B. ${\displaystyle B\in {\mathfrak {B}}}$ ${\displaystyle p_{1},p_{2}\in {\mathfrak {p}}}$
• If a subset of the point set is an incidence structure, then the set of all blocks that are incised with each point of this subset is noted as; if the incidence structure is finite, then the number of these blocks is noted as. The symbols and are accordingly explained dual as point sets or their number for sets of blocks of a (finite) incidence structure. Formally: ${\displaystyle {\mathfrak {m}}\subseteq {\mathfrak {p}}}$ ${\displaystyle ({\mathfrak {m}})}$ ${\displaystyle [{\mathfrak {m}}]=|({\mathfrak {m}})|}$ ${\displaystyle ({\mathfrak {M}})}$ ${\displaystyle [{\mathfrak {M}}]}$ ${\displaystyle {\mathfrak {M}}\subseteq {\mathfrak {B}}}$

${\displaystyle ({\mathfrak {m}})=\{B\in {\mathfrak {B}}\mid \forall p\in {\mathfrak {m}}\colon \;p{\mathrel {\ I\ }}B\},\quad ({\mathfrak {M}})=\{p\in {\mathfrak {p}}\mid \forall B\in {\mathfrak {M}}\colon \;p{\mathrel {\ I\ }}B\}.}$

• From the definition it follows that the set of all blocks means if the empty set is regarded as a subset of the point set, and the set of all points means if it is regarded as a subset of the block set. ${\displaystyle (\emptyset )}$

Parameters of a finite incidence structure, point and block degree

The following parameters are assigned to a finite incidence structure for and : ${\displaystyle i\in \{0,1,\ldots ,|{\mathfrak {p}}|\}}$ ${\displaystyle j\in \{0,1,\ldots ,|{\mathfrak {B}}|\}}$

${\displaystyle b_{i}:={\binom {|{\mathfrak {p}}|}{i}}^{-1}\cdot \sum _{{\mathfrak {m}}\subseteq {\mathfrak {p}} \atop |{\mathfrak {m}}|=i}[{\mathfrak {m}}],\quad v_{j}:={\binom {|{\mathfrak {B}}|}{j}}^{-1}\cdot \sum _{{\mathfrak {M}}\subseteq {\mathfrak {B}} \atop |{\mathfrak {M}}|=j}[{\mathfrak {m}}].}$

The parameter thus indicates how many blocks are incising on average with different points and the parameter indicates how many points are on average on different blocks at the same time. The parameter is the total number of points and the total number of blocks of the finite incidence structure. ${\displaystyle b_{i}}$ ${\displaystyle i}$ ${\displaystyle v_{j},}$ ${\displaystyle j}$ ${\displaystyle v=v_{0}}$ ${\displaystyle b=b_{0}}$

In addition , the term degree is defined , especially in connection with linear spaces :

• The degree of a point is the number of blocks with which it is incised. ${\displaystyle r_{p}}$ ${\displaystyle p}$ ${\displaystyle p}$
• The degree of a block or a straight line is the number of points with which it is incised. ${\displaystyle d_{B}}$ ${\displaystyle B}$ ${\displaystyle B}$

This is the average of all degrees of points and the average of all degrees of blocks. ${\displaystyle v_{1}}$ ${\displaystyle b_{1}}$

Regularity conditions and types of finite incidence structures

For a finite incidence structure, the following regularity conditions are defined, based on which these structures can be classified:

${\displaystyle (\mathrm {P} _{i})}$Each different points incise with exactly blocks. In other words, for all the -element subsets applies ${\displaystyle i}$ ${\displaystyle b_{i}>0}$ ${\displaystyle i}$ ${\displaystyle {\mathfrak {m}}\subseteq {\mathfrak {p}}}$ ${\displaystyle [{\mathfrak {m}}]=b_{i}>0.}$

${\displaystyle (\mathrm {B} _{j})}$Different blocks each incise with exactly points. In other words, for all the -element subsets applies ${\displaystyle j}$ ${\displaystyle v_{j}>0}$ ${\displaystyle j}$ ${\displaystyle {\mathfrak {M}}\subseteq {\mathfrak {B}}}$ ${\displaystyle [{\mathfrak {M}}]=v_{j}>0.}$

• A finite incidence structure that satisfies the regularity conditions and , but neither the condition nor the condition is called an incidence structure of type . ${\displaystyle (\mathrm {P} _{1}),\ldots ,(\mathrm {P} _{m})}$ ${\displaystyle (\mathrm {B} _{1}),\ldots ,(\mathrm {B} _{n})}$ ${\displaystyle (\mathrm {P} _{m+1})}$ ${\displaystyle (\mathrm {B} _{n+1}),}$ ${\displaystyle (m,n)}$
• A finite incidence structure that fulfills (at least) the regularity conditions is called a tactical configuration (according to Moore). Typical examples are the generalized quadrilaterals . ${\displaystyle (\mathrm {P} _{1}),(\mathrm {B} _{1})}$
• A finite incidence structure that satisfies with the parameter is called the incidence geometry . ${\displaystyle (\mathrm {P} _{2})}$ ${\displaystyle b_{2}=1}$

Incidence matrix

→ The term incidence matrix described here for a finite incidence structure can be viewed as a generalization of the term incidence matrix of an undirected graph .

A finite incidence structure with dots and blocks may also be a - matrix are represented. To do this, number the points from to and the blocks from to and enter the relationships between the points and the blocks in the matrix: ${\displaystyle v\geq 1}$ ${\displaystyle b\geq 1}$ ${\displaystyle v\times b}$ ${\displaystyle 1}$ ${\displaystyle v}$ ${\displaystyle 1}$ ${\displaystyle b}$

${\displaystyle a_{ij}:={\begin{cases}1,&{\text{ falls }}(p_{i},B_{j})\in I,\\0,&{\text{ sonst}}.\end{cases}}}$

The matrix is then called an incidence matrix of the finite incidence structure. ${\displaystyle A=(a_{ij})_{1\leq i\leq v;\;1\leq j\leq b}}$

Of course, different numbering of the point and block sets generally yield different incidence matrices. Obviously every matrix whose elements are only and is an incidence matrix of a suitable finite incidence structure, and this is completely determined by the incidence matrix. ${\displaystyle 0}$ ${\displaystyle 1}$

Incidence matrices are also used, especially in connection with Hadamard matrices , in which the entries in the matrix described above are replaced by. ${\displaystyle (1,-1)}$ ${\displaystyle 0}$ ${\displaystyle -1}$

Deriving an incidence structure

For a finite or infinite incidence structure for a point is referred to the following structure as defined deriving after or at the point derived incidence structure ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ ${\displaystyle x\in {\mathfrak {p}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle x}$ ${\displaystyle x}$

${\displaystyle {\mathcal {I}}_{x}=({\mathfrak {p}}\setminus \{x\},(x),I_{\mathrm {ind} }).}$

The derivation according to consists of all points except as a point set the blocks through as a block set with the induced incidence . In this case, it is referred to as an extension of An extension is in general (like the “derivation” as the inversion of the “derivation” in other areas mathematics) is not clearly determined by the original structure without additional conditions. ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle {\mathfrak {p}}_{x}={\mathfrak {p}}\setminus \{x\},}$ ${\displaystyle x}$ ${\displaystyle {\mathfrak {B}}_{x}=(x)=\{B\in {\mathfrak {B}}\mid x{\mathrel {\ I\ }}B\}}$ ${\displaystyle I_{\mathrm {ind} }=I\cap ({\mathfrak {p}}_{x}\times {\mathfrak {B}}_{x}).}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}_{x}.}$

The term is used, for example, when conclusions are drawn from the non-existence of block plans with certain parameters that there are certain larger block plans.

How the derivation can affect the parameters of special incidence structures is exemplified in the article Wittscher block plan , there in particular in the section incidence parameters of Witt block plans .

example

If the incidence structure is a Möbius plane , the derivation is an affine plane at every point and thus a simpler structure (see Möbius plane ). ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$

properties

Principle of duality

• If a statement is valid for all incidence structures of a class , then the dual statement is valid for all incidence structures ${\displaystyle A}$ ${\displaystyle K}$ ${\displaystyle A^{D}}$ ${\displaystyle K^{D}.}$
• If there is a class of incidence structures , one says “ the principle of duality applies to”. Then for every statement that applies to all incidence structures , it is also correct for all of these incidence structures. ${\displaystyle K}$ ${\displaystyle K=K^{D}}$ ${\displaystyle K}$ ${\displaystyle A,}$ ${\displaystyle K}$ ${\displaystyle A^{D}}$

Examples

The duality principle applies to the class

• the finite incidence structures,
• of the incidence structures in which each point is incised with a constant number of blocks and each block is incised with a constant number of points,
• the projective planes ,
• the projective planes of Lenz class VII (these are exactly the Desargue projective planes ),
• the finite incidence structures, the incidence matrix of which can be chosen as a symmetric matrix .

The last two classes mentioned contain structures that are dual to themselves only . Therefore, the duality principle applies here in its tightened form: For every statement that applies in one of these structures, the dual statement in the same structure applies .

Counterexamples

The duality principle does not apply to the class

• the incidence structures with a finite point set,
• the simple incidence structures,
• the degenerate incidence structures,
• the incidence structures in which each point with blocks and each block with incised dots there, unless it is , ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m=n}$
• the affine planes ,
• of the projective planes of Lenz class IVa.

Relationships between parameters

The following is a finite incidence structure. Then according to the principle of double counting : ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$

• ${\displaystyle \sum _{p\in {\mathfrak {p}}}[p]=\sum _{B\in {\mathfrak {B}}}[B],}$
• The principle of double counting expressed by parameters is: ${\displaystyle v_{0}\cdot b_{1}=v_{1}\cdot b_{0}.}$

The following two equations, which are dual to one another, allow all parameters of a finite incidence structure to be calculated if the number of blocks for each point and the number of points for each block are known: ${\displaystyle [p]}$ ${\displaystyle [B]}$

• ${\displaystyle \sum _{B\in {\mathfrak {B}}}{\binom {[B]}{i}}={\binom {v}{i}}\cdot b_{i}{\;}}$ for all ${\displaystyle {\;}i\in \{0,1,\ldots ,v\}.}$
• ${\displaystyle \sum _{p\in {\mathfrak {p}}}{\binom {[p]}{j}}={\binom {b}{j}}\cdot v_{j}{\;}}$ for all ${\displaystyle {\;}j\in \{0,1,\ldots ,b\}.}$
• If the incidence structure fulfills the regularity condition , that is, applies to every block, then the first formula simplifies to ${\displaystyle (\mathrm {B} _{1})}$ ${\displaystyle [B]=v_{1}>0}$ ${\displaystyle b_{i}={\binom {v}{i}}^{-1}\cdot b\cdot {\binom {v_{1}}{i}}.}$
• If the incidence structure fulfills the regularity condition , that is, applies to every point, then the second formula simplifies to ${\displaystyle (\mathrm {P} _{1})}$ ${\displaystyle [p]=b_{1}>0}$ ${\displaystyle v_{j}={\binom {b}{j}}^{-1}\cdot v\cdot {\binom {b_{1}}{j}}.}$

The following two inequalities, which are also dual to one another, for arbitrary finite incidence structures were proven by Dembowski :

• ${\displaystyle b_{i}\cdot (v_{1}-i)\leq b_{i+1}\cdot (v-i){\;}}$ for all ${\displaystyle {\;}i\in \{0,1,\ldots ,v\}.}$
• ${\displaystyle v_{j}\cdot (b_{1}-j)\leq v_{j+1}\cdot (b-j){\;}}$ for all ${\displaystyle {\;}j\in \{0,1,\ldots ,b\}.}$
• If the incidence structure has the type and then holds for all nonnegative numbers . ${\displaystyle (m,n),\;m,n\geq 2}$ ${\displaystyle I\neq {\mathfrak {p}}\times {\mathfrak {B}}.}$ ${\displaystyle i\colon \;v_{i}=b_{i}}$

Regularity constraints

• The validity of and follows from the validity of ${\displaystyle (\mathrm {P} _{m})}$ ${\displaystyle (\mathrm {B} _{1})}$ ${\displaystyle (\mathrm {P} _{m-1}),\ldots ,(\mathrm {P} _{1}).}$
• The validity of and follows from the validity of ${\displaystyle (\mathrm {B} _{n})}$ ${\displaystyle (\mathrm {P} _{1})}$ ${\displaystyle (\mathrm {B} _{n-1}),\ldots ,(\mathrm {B} _{1}).}$
• If the type is a non-degenerate, finite incidence structure, then or or ${\displaystyle (m,n)}$ ${\displaystyle m\leq 1}$ ${\displaystyle n\leq 1}$ ${\displaystyle m=n=2.}$

Properties of the incidence structure based on the incidence matrix

• Are finite incidence structures by the incidence matrices and can be described, this incidence structures are isomorphic if the two matrices of the same type are and a line permutation ( the symmetric group on elements) and a column permutation exist that allow for true . ${\displaystyle {\mathcal {I}},{\mathcal {J}}}$ ${\displaystyle A=(a_{ij})}$ ${\displaystyle B=(b_{ij})}$ ${\displaystyle v\times b,\;v,b\in \mathbb {N} }$ ${\displaystyle \pi \in S_{v}}$ ${\displaystyle S_{v}}$ ${\displaystyle v}$ ${\displaystyle \rho \in S_{b}}$ ${\displaystyle a_{\pi (i)\rho (j)}=b_{ij}}$ ${\displaystyle 1\leq i\leq v,\;1\leq j\leq b}$

• In particular, two different incidence matrices can describe the same incidence structure precisely if one can be transformed into the other by such row and column permutations.

• A finite incidence structure is simple if and only if no two columns of one and therefore of every incidence matrix for the structure coincide with one another.
• A finite incidence structure has degenerated if and only if a column of one and therefore every incidence matrix for the structure contains at most one 0.
• The dual of a finite incidence structure with incidence matrix A can be described by the transposed incidence matrix . ${\displaystyle A^{T}}$

• In particular, a finite incidence structure is isomorphic to its dual structure if and only if its incidence can be described by a symmetric matrix.

Examples

• A trivial rank 2 geometry (in the sense of the Buekenhout-Tits geometry ) consists of a non-empty set of points and blocks with the incidence relation . For example, the residual of a certain straight line g in a three-dimensional affine or projective space is such an incidence structure: Every point on the straight line g (i.e. every “point” of the point set ) incurs with every plane through this line (i.e. every “block” of the block set ) and vice versa. These incidence structures are degenerate and (if point and block sets each contain more than one element) not simple. It should be noted that such incidence structures occurring in geometric contexts are generally not incidence geometries . ${\displaystyle {\mathfrak {p}},{\mathfrak {B}}}$ ${\displaystyle I={\mathfrak {p}}\times {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {B}}}$
  • If such a trivial incidence structure is finite, then it has the type your parameters are and ${\displaystyle |{\mathfrak {p}}|=v\geq 2,\;|{\mathfrak {B}}|=b\geq 2}$ ${\displaystyle (v,b).}$ ${\displaystyle b=b_{0}=b_{1}=\cdots =b_{v}}$ ${\displaystyle v=v_{0}=v_{1}=\cdots =v_{b}.}$

• The structure of incidence is simple by construction, its dual structure of incidence is not, because points 1 and 2 incise with the same blocks. An incidence matrix is: ${\displaystyle (\{1,2,3\},\{\emptyset ,\{1,2\},\{1,2,3\}\},\in )}$

${\displaystyle {\Bigl (}{\begin{smallmatrix}0&1&1\\0&1&1\\0&0&1\end{smallmatrix}}{\Bigr )}.}$

• The structure of the incidence is simple by design. It is not degenerate, but the dual incidence structure is degenerate and not simple. An incidence matrix is: ${\displaystyle (\{1,2,3\},\{\{3\}\},\in )}$

${\displaystyle {\Bigl (}{\begin{smallmatrix}0\\0\\1\end{smallmatrix}}{\Bigr )}.}$

• An incidence structure , in which all points incise with the single block, is simple and degenerate. Is the set of points is finite and the number of its points, it is a weak affine space and has the type ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},\{{\mathfrak {p}}\},\in )}$ ${\displaystyle m=|{\mathfrak {p}}|}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle (m,1).}$

• A finite projective plane is a non-degenerate incidence structure of the type ${\displaystyle (2,2).}$

• A non-degenerate, finite incidence structure of the type is a - block diagram . Parameters are then ${\displaystyle (t,n),\;t,n\geq 1,}$ ${\displaystyle t-(v,k,\lambda )}$ ${\displaystyle v_{0}=v,\;b_{1}=k,\;b_{t}=\lambda .}$

• A network is always an incidence structure of the type . If and only if is, the network is even an affine plane . ${\displaystyle (m,1),\;m\in \{1,2\}}$ ${\displaystyle m=2}$

• The axioms of a linear space can partly be formulated by a regularity condition and by demands on the parameters of the incidence structure : The condition must be fulfilled and it must be. In addition, there is the requirement that there must be (every straight line ) for every block . ${\displaystyle {\mathcal {L}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle (\mathrm {P} _{2})}$ ${\displaystyle b_{2}=1}$ ${\displaystyle b_{0}\geq 2}$ ${\displaystyle B\in {\mathfrak {B}}\;[B]\geq 2}$
  • A near pencil with points is a special linear space, it can be described as an incidence structure by the point set and the block set with the containing relation as incidence (cf. linear space (geometry) #examples ). A near pencil is simple, degenerate and isomorphic to its dual structure. It fulfills the regularity conditions with the parameters but (except for ) neither nor . For example, the near pencil with four points has the incidence matrix ${\displaystyle v\geq 3}$ ${\displaystyle {\mathfrak {p}}=\{1,2,3,\ldots ,v\}}$ ${\displaystyle {\mathfrak {B}}=\{\{2,3,\ldots ,v\},\;\{1,2\},\{1,3\},\ldots \{1,v\}\}}$ ${\displaystyle (\mathrm {P} _{2}),(\mathrm {B} _{2})}$ ${\displaystyle b_{2}=v_{2}=1}$ ${\displaystyle v=3}$ ${\displaystyle (\mathrm {P} _{1})}$ ${\displaystyle (\mathrm {B} _{1})}$

${\displaystyle {\biggl (}{\begin{smallmatrix}0&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\end{smallmatrix}}{\biggr )}.}$

• Every undirected graph in the sense of graph theory can be viewed as a special finite incidence structure by considering the nodes of the graph as points and the edges as blocks . A finite incidence structure is exactly then an undirected graph, where each block is incident with exactly two points, for an incidence matrix that is: In each column exactly two entries are otherwise only ${\displaystyle 1,}$ ${\displaystyle 0.}$

literature

• Thomas Beth , Dieter Jungnickel , Hanfried Lenz : Design Theory . 2nd Edition. BI Wissenschaftsverlag, London / New York / New Rochelle / Melbourne / Sidney 1999, ISBN 0-521-33334-2 .
• Albrecht Beutelspacher : Introduction to Finite Geometry . I. Block plans. BI Wissenschaftsverlag, Mannheim / Vienna / Zurich 1982, ISBN 3-411-01632-9 , Chapter 1. Basics.
• Peter Dembowski : Combinatorial Properties of Finite Incidence Structures . In: Mathematical Journal . tape 75 , no. 1 , 1961, pp. 256-270 , doi : 10.1007 / BF01211024 .
• Eliakim Hastings Moore : Tactical memoranda . In: American Journal of Mathematics . tape 18 , no. 3 , 1896, p. 264-290 , JSTOR : 2369797 .

References and comments

1. ↑ ^{a b c d} Beutelspacher (1982), Section 1.2 Incidence structures
2. ↑ In geometry the incidence relation is often introduced symmetrically ; by the definition here it is antisymmetric . The symmetrical incidence is obtained from the anti-symmetric I through and vice versa . ${\displaystyle I^{\ast }}$ ${\displaystyle I^{\ast }=I\cup I^{-1}}$ ${\displaystyle I=I^{\ast }\cap ({\mathfrak {p}}\times {\mathfrak {B}})}$
3. ^ Klaus Metsch: Linear Spaces with Few Lines . Springer, Berlin / Heidelberg / New York / London / Paris / Tokyo / Hong Kong / Barcelona / Budapest 1991, ISBN 3-540-54720-7 , pp. 1 .
4. ↑ ^{a b c} Dembowski (1961)
5. ^ Moore (1896)
6. ↑ Beutelspacher (1982), p. 41.
7. ^ Beth, Jungnickel, Lenz, I §9: Hadamard designs
8. ↑ English: derived structure at a point (Beth, Jungnickel, Lenz, Definition I.9.8) ${\displaystyle x}$
9. ↑ ^{a b} Beutelspacher (1982), 4th non-existence sentences
10. ↑ For the Desargue planes: Albrecht Beutelspacher, Ute Rosenbaum: Projective Geometry . From the basics to the applications (=  Vieweg Studium: advanced course in mathematics ). 2nd, revised and expanded edition. Vieweg, Wiesbaden 2004, ISBN 3-528-17241-X ( table of contents [accessed on August 10, 2013]).
11. ↑ This formula is based on the fact that the number of all incidences is on both sides of the equation . Sorted on the left according to the points involved in the incidence and on the right according to the blocks involved , Beutelspacher (1982), Lemma 1.2.3 ${\displaystyle |I|}$
12. ↑ Beutelspacher (1982), main clause 1.2.9
13. ↑ Note that here - for a degenerate incidence structure - also or can occur, Beutelspacher (1982), Corollary 1.3.3 ${\displaystyle m>2}$ ${\displaystyle n>2}$
14. ↑ In general it doesn't have to be! The condition is violated. Bag Spacher (1982) ${\displaystyle v=b}$ ${\displaystyle I\neq {\mathfrak {p}}\times {\mathfrak {B}}}$