Incidence structure

The term incidence structure referred to in mathematics, especially in geometry, a structure consisting of a set of points and a set of blocks in geometric contexts, the blocks are also referred to as straight lines. Between these disjoint sets an incidence relation is defined. Through these weak demands numerous complicated structures turn out to be special cases of incidence structures. Some of these relationships are described in this article called (→ in the Examples section ). For important classes of incidence structures, a duality principle. The finite incidence structures are objects of study in finite geometry and therefore also in combinatorics. You can assign a finite set of parameters that specify, for example, how many blocks are incident two different points on average; finite incidence structure in which such a parameter, not only the average value, but indicates the actual number of incidence in each case, performs a regularity. Non- degeneracy incidence structures satisfying such Regularitätsbedingen can be typified by this.

• 2.1 Principle of Duality
• 2.2 Relationships between the parameters
• 2.3 regularity conditions
• 2.4 Properties of the incidence structure using the incidence matrix

Definitions

An incidence structure is a triple of sets with

The elements of hot points of blocks. The elements of are called the incidence or flags. For one writes and says that the point is incident with the block.

Isomorphisms of incidence structures

Be and incidence structures. A bijection is called an isomorphism of the, if:

Simple incidence structure

The incidence structure is called simple if for arbitrary blocks:

So when all blocks are completely determined by the inzidierenden with them points. Is equivalent to this: is simple if and only if is isomorphic to an incidence structure in which a subset of the power set of is.

Duality

• At an incidence structure of the dual incidence structure is formed:

• You swapped in a statement A on incidence structures, the words "point" and " block ", we obtain the dual to A testimony.

• For a class of incidence structures is denoted by the class of dual incidence structures.
• A specific incidence structure is called to be self-dual if there is an isomorphism. In other words, if and only dual to itself when the duality principle for the class of structures isomorphic to apply.

Notation and basic concepts

• 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 are not incident with this block, otherwise called the structure does not degenerate. An incidence structure is so if and only non-degenerate if exist for each block at least two different points that are not incident with B.
• Is a subset of the set of points an incidence structure, then the set of all blocks incident with each point of this subset, as quoted; the incidence structure finally, the number of these blocks is used as noted. The symbols and are accordingly as dual sets of points or the number of sets of blocks of a (finite) incidence structure explained. Formal:

• From the definition it follows that the set of all blocks means that if the empty set is considered as a subset of the point set, and the set of all points, when viewed as a subset of the block amount.

Parameters of a finite incidence structure, point and block level

A finite incidence structure can be assigned for the following parameters:

The parameter thus indicates how many blocks are incident with an average of i different points and the parameter determines how many points are on j different blocks on average at the same time. Said parameter is the total number of points, and the total number of blocks of finite incidence structure.

In addition, it is mainly related to vector spaces, defines the term degree:

• The level of a point is the number of blocks, which is incident p.
• The degree of a block or a line, the number of points, which is incident with B.

This is the average of all grades of points and the average of all grades of blocks.

Regularity conditions and types of finite incidence structures

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

• Finite incidence structure satisfying the regularity and, but not the condition or the condition is referred to as the incidence -type structure.
• Finite incidence structure, the (at least) meet the regularity is referred to as a tactical configuration ( according to Moore). Typical examples are the generalized squares.
• Finite incidence structure, filled with the parameter is the incidence geometry.

Incidence matrix

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

Finite incidence structure with dots and blocks may also be represented by a matrix. These numbered the points up and the blocks up and carries through into the matrix relations between the points to blocks one:

The matrix is then called an incidence matrix of finite incidence structure.

Of course, different numbering of point - and block amount generally provide different incidence matrices. Clearly, any matrix whose elements are only 0 and 1, the incidence matrix of a suitable finite incidence structure and it is completely determined by the incidence matrix.

There are, especially in the context of Hadamard matrices and (1, -1) incidence matrices used in which the entries are 0 in the matrix described above is replaced by -1.

Deriving an incidence structure

For a finite or infinite incidence structure is known for a point below the structure defined as the derivative with respect to x, or from the point of incidence of x -derived structure

The derivative with respect to x is therefore from all points other than x and point size of the blocks as a block by x amount with the induced incidence, in this case is referred to as extension. An extension is ( "discharge" in other areas of mathematics as well as the " Aufleitung " as the reverse of ) is not uniquely determined without additional conditions by the original structure in general.

The term is used, for example, when it is inferred from the non-existence of block diagrams of certain parameters on certain larger block diagrams.

As the derivation can affect the parameters of special incidence structures, is exemplified in the article Witt cutter plan, there is shown the incidence parameter Wittschen block plans, particularly in the section.

Properties

Principle of duality

• If A is a statement that applies to all incidence structures of a class K, the dual statement for all incidence structures applies from
• If for a class K of incidence structures, so they say " for K the duality principle applies ." Then is right for every statement A, which is true for all incidence structures of K, for all these incidence structures.

The duality principle is valid for the class

• Of finite incidence structures
• The incidence of structures in which each point is incident with a constant number of blocks, each block having a constant number of dots,
• Of projective planes,
• Of projective planes of Lenz -Class VII ( these are precisely the Desargues projective planes ),
• Of finite incidence structures, whose incidence matrix can be chosen as a symmetric matrix.

The two last-named classes contain only to be self-dual structures. So here applies the principle of duality in its stricter form: For each statement that is true in one of these structures, meets the dual statement in the same structure.

The duality principle does not apply to the class

• The incidence structures with a finite set of points,
• The simple incidence structures
• The degenerate incidence structures
• The incidence of structures in which each point of m blocks, and each block of n points incised unless it is
• Of affine planes

Relations between the parameters

In the following, a finite incidence structure. Then by the principle of double counting:

• ,
• The principle of double counting is expressed by parameters.

Both of the following, each dual equations make it possible to calculate all the parameters of a finite incidence structure, when the number of blocks for each point, and the number of points for each block are known:

• For all
• For all
• Meets the incidence structure, the regularity condition, that is, valid for each block, then the first formula simplifies to
• Meets the incidence structure, the regularity condition, that is, for any point, then the second formula simplifies to

The following two are also mutually dual inequalities for arbitrary finite incidence structures were proved by Dembowski:

• For all
• For all
• Has the incidence structure and the type is. Then for all non-negative integers i: .

Regularity conditions

• From the validity of and follows the validity of.
• From the validity of and follows the validity of.
• If the type is a non-degenerate, finite incidence structure, then apply or or

Properties of the incidence structure using the incidence matrix

• Are finite incidence structures by the incidence matrices and can be described, then these incidence structures are isomorphic if and only if the two matrices are the same type and a row permutation (the symmetric group on v elements ) and a column permutation exist that allow for applies.

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

• A finite incidence structure is simple if and only if no two columns a and thus any incidence matrix for the structure coincide.
• A finite incidence structure is then degenerate exactly when a column a and thus any incidence matrix for the structure contains at most one 0.
• The dual structure with a finite incidence incidence matrix A can be described by the transposed matrix incidence.

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

Examples

• A trivial rank 2 geometry ( in the sense of Buekenhout - Tits geometry ) is a non-empty point and block size, with the incidence relation. For example, the residue of a given line g in a three-dimensional affine or projective space such an incidence structure: Each point on the line g (ie, each "point" of the point set ) is incident with each level by this line (ie each " block " of the block quantity ) and vice versa. This incidence structures are degenerated and (if point - block and lot more each than one element ) is not easy. It is noted that such structures incidence occurring in the geometric relationships are generally no incidence geometry.

• If such a trivial incidence structure finite, then it has the type. Your parameters are and.

• The incidence structure is by design simple, their dual incidence structure, it is not, because the points 1 and 2 are incident with the same blocks. An incidence matrix is
• The incidence structure is simple by design. It is non-degenerate, but the dual incidence structure is degenerated and not easy. An incidence matrix is
• An incidence structure in which all points are incident so with the single block is simple and degenerate. If the point set is finite and the number of points, so is a weakly affine space and has the type
• A finite projective plane is a nondegenerate incidence structure of type
• A nondegenerate, finite incidence structure of the type is a block diagram. Parameters are then
• A network is always an incidence structure of the type. Just when is the net is even an affine plane.
• The axioms of a linear space can be formulated in part by a regularity condition and claims on the parameters of the incidence structure: The condition must be met with, and it needs to be. Add to this the requirement that for each block ( each line ) needs to be.

• A near pencil with points is a special vector space, it can be as incidence structure by the point set and the block set with the Contained incidence relation as described (see Linear space ( geometry) # examples). A near pencil is easy to degenerate and isomorphic to its dual structure. It meets the regularity conditions with the parameters but (except for ) neither. The near pencil with 4 points has, for example, the incidence matrix

• Each undirected graph in terms of graph theory can be regarded as special finite incidence structure by perceives the nodes of the graph as the edge points as blocks. A finite incidence structure is an undirected graph if and only if each block is incident with exactly two points, that is, for an incidence matrix: each column contains exactly two entries 1, otherwise only 0