An incidence structure is a triple D = (P,B,I), where:
A near-linear space is an incidence structure in which every block contains at least two points and any two points lie in at most one block. A linear space is a near-linear space in which any two points lie in exactly one block. It is usual, when discussing near-linear spaces, to use the term line in place of the term block.
Let v, k, t and λ be integers with v ≥ k ≥ t ≥ 0 and λ ≥ 1. A t-design with v points and blocksize k is an incidence structure D = (P,B,I) where:
Such a design is usually referred to as a t-(v,k,λ) design. If b denotes the cardinality of B, a t-design with v = b and t ≥ 2 is called a symmetric design.
In the following text, operations described for incidence structures also apply to near-linear spaces, linear spaces, and block designs unless otherwise noted.
An incidence structure is usually constructed by giving the parameters together with a list of blocks; an alternative is to give the incidence matrix. Functions are provided to construct incidence structures from graphs and codes. Given an incidence structure, other incidence structures may be derived using a number of standard operations: complement, dual, contract at a point of block, residual with respect to a point or block, and restriction to a specified set of points. Given two or more incidence structures their sum or union may be constructed.
Various tests are available for determining basic properties of an incidence structure D. These include simple, self-dual, uniform, balanced, complete, symmetric, point regular, block regular, near-linear space, linear space, design, and Steiner. Testing t-balance can be expensive and so, as well as a brute force algorithm, two alternatives are provided. One alternative algorithm first computes the automorphism group A of D and then uses the A-orbits of t-sets of elements chosen from P to reduce the amount of testing required. Another alternative is a brute force algorithm optimised for t ≥ 4.
Let G be a group of order v and let k and λ be positive integers such that 1 < k < v. A (v,k,λ) difference set for G is a set D of k group elements such that the set
A function is provided to construct difference sets belonging to the families "Q", "H6", "T", "B", "B0", "O", "O0", or "W4" as listed in Marshall Hall's book, Combinatorial Theory. Another function is provided for constructing the Singer difference set corresponding to a hyperplane of PG(n,q).
Given a difference set whose elements belong to an integer residue class ring, a finite abelian group, or a finite group, a function is provided that constructs the corresponding symmetric design.
Let D be an incidence structure with v points. A resolution of D is a partition of the blocks of D into classes Ci such that each class is a 1-design with v points and index λ. The positive integer λ is called the index of the resolution. A resolution with λ = 1 is called a parallelism. In this case the classes Ci are called parallel classes.
An incidence structure can be tested to determine whether of not it has a resolution of any index or a resolution having a particular index. It is also possible to obtain all resolutions. Given a uniform incidence structure a function is provided to search for a parallelism. A variant will return all parallelisms. It is also possible to determine the parallel classes. The basic algorithm employs a backtrack search which is efficient when the design has a parallelism. If it is suspected that there are no parallelisms an alternative algorithm that works by searching for cliques in a graph will be much faster. For example, in the case of a non-parallelisable design with 272 blocks, the clique method was an order of magnitude faster than the backtrack method (0.02 seconds as compared to 0.2 seconds).
A particularly important function for incidence structures is the construction of its automorphism group. Magma uses a very efficient backtrack search algorithm developed by J. Leon which employs his partition refinement technique. A variation of this algorithm is used to test pairs of incidence structures for isomorphism.
The automorphism group of an incidence structure D is returned as a permutation group G acting on a set which is determined by properties of D. The Magma G-set machinery may be used to obtain the action of G on different sets associated with D. The two most important actions are those acting on the point set and block set. As the group G does not directly act on D, elements of G that are required to act on D are first cast as mappings of D into itself.
The concept of a block design arises in many different areas of discrete mathematics and coding theory as well as in other areas such as group theory. Consequently, the Magma machinery for incidence structures has been heavily used across a wide range of areas. Frequently, in a project that involves calculations with designs, the design aspect forms a small part of a project based in a different area altogether. However, there are many projects known to us that employed the Magma machinery to gain insight into problems in design theory.
An example of a project that has used the design machinery extensively over the 20 year life of Magma is the long-running project of E. Assmus and J. Key in which they study the application of algebraic coding theory to the analysis and construction of designs. Details may be found in the book Designs and their Codes by Assmus and Key.