15 Finite Incidence Structures

15.1 Enumerative Combinatorics

• Factorial

• Binomial, multinomial coefficients

• Stirling numbers of the first and second kind

• Fibonacci numbers, Bernoulli numbers, Harmonic numbers, and Eulerian numbers

• Number of partitions of n

• Enumeration of restricted and unrestricted partitions

• Sets of subsets, multisets, and subsequences of sets

• Permutations of sets (as sequences)

15.2 Partitions and Young Tableaux

Extensive facilities were installed for working with Young tableaux and symmetric functions. The facility is heavily based on the Symmetrica package developed by A. Kerber and associates in Bayreuth. A highlight of the tableau machinery is the Robinson-Schensted-Knuth (RSK) correspondence. The collection of all symmetric functions defined over some ring is viewed as forming an algebra where the chief interest lies in the change of basis matrix relative to different bases. The Young tableaux code was written by G. White while the machinery for symmetric functions was adapted from Symmetrica by A. Kohnert (Bayreuth) during a year-long visit to Sydney.

• Number of partitions of n

• Enumeration of restricted and unrestricted partitions

• Conjugate partitions

• Longest increasing sequences within words of integers

• Lexicographical ordering of words

• Creation of skew or non-skew tableaux over the integers or arbitrary label sets

• Enumeration of tableaux

• Random tableaux

• Properties: shape, skew-shape, weight, hooklength's, content, row/column words

• Operations: diagonal sum, product, conjugate, jeu de taquin, row insertion, inverse jeu de taquin, inverse row insertion

• RSK correspondence, inverse RSK correspondence

• Enumeration of tableaux having specified size and alphabet

15.3 Symmetric Function Algebras

Symmetric functions are defined as polynomials in an infinite number of variables, invariant under the action of the symmetric group. The set of all symmetric functions denoted by Λ is an algebra. A symmetric function algebra may be created over an arbitrary commutative ring (with unity) R. Five different bases for an algebra of symmetric functions are supported.

• Creation of algebras with any one of 5 possible bases: consisting of Schur functions, Elementary, Monomial, Homogeneous (complete) or Power Sum functions.

• Creation of elements as linear combinations of basis elements (indexed by partitions) or from coercing a polynomial or a scalar.

• An algebra can be tested for which basis it represents its elements with respect to.

• Alternative print styles for elements of an algebra

• Addition, subtraction, multiplication and composition (plethysm) of symmetric functions. Testing for homogeneity and equality.

• Decomposition of symmetric functions into basis elements and coefficients thereof.

• Symmetric functions can be coerced into polynomial rings.

• Frobenius homomorphism, inner product, tableax with a given generating function and corresponding characters

• Matrices converting from any of the 5 bases to any other of the 5 bases

15.4 Graphs

Graphs may be directed or undirected. In addition, their vertices and/or their edges may be labelled. A graph may be represented by means of its adjacency matrix. or by means of its adjacency list.

• Directed and undirected graphs

• Optional vertex and edge labels

• Operations: union, join, product, contraction, switching etc

• Standard graphs: complete, complete bipartite, k-cube

• Properties: connected, regular, eulerian

• Algebraic invariants: Characteristic polynomial, spectrum

• Diameter, girth, circumference

• Connectedness, paths and circuits

• Triconnectivity

• General vertex and edge connectivity in graphs and digraphs

• MaximumMatching in bipartite graphs

• Spanning trees, cut-vertices

• Cliques and maximal cliques, independent sets

• Chromatic number, chromatic index, chromatic polynomial

• Planarity testing, obstruction isolation, faces, embedding

• Graphs from groups: Cayley graph, orbital graph

• Automorphism group (B. McKay's algorithm), canonical labelling

• Testing of pairs of graphs for isomorphism

• Group actions on a graph: orbits and stabilizers of vertex and edge sequences

• Symmetry properties: vertex transitive, edge transitive, k-arc transitive, distance transitive, distance regular

• Intersection numbers of a distance regular graph

• Interface for B. McKay's graph generation algorithm [McK98]

Brendan McKay's automorphism program nauty [McK81] is used for computing automorphism groups and for testing pairs of graphs for isomorphism. In accordance with the Magma philosophy, a graph may be studied under the action of an automorphism group. Using the G-set mechanism an automorphism group can be made to act on any desired set of objects derived from the graph.

The planarity tester and obstruction isolator are linear time algorithms; they are due to Boyer and Myrvold [BW01].

The triconnectivity algorithm is the classical linear time algorithm from Hopcroft and Tarjan [HopTar73] with corrections of our own and from Gutwenger and Mutzel [GutMut01].

The general vertex and edge connectivity machinery rests on two flow-based algorithms for networks: the Dinic algorithm and the push-relabel method (see below).

15.5 Networks

A network is a digraph whose edges are associated with a capacity. It may have multiple (i.e. parallel) edges and loops. A network is represented by means of its adjacency list.

• Operations: union, join, contraction

• Maximum flow and minimum cut

There are two implementations of the maximum flow algorithm. One is the classical Dinic algorithm with heuristics due to McKay, the other is a push-relabel method with heuristics mainly due to Cherkassky and Golberg et al. [CG97, CGM98].

15.6 Incidence Structures and Designs

General incidence structures provide a universe in which families of incidence structures satisfying stronger conditions (linear spaces, t-designs, etc) reside.

• Creation of a general incidence structure, near-linear space, linear space, design

• Difference sets: standard difference sets, development

• Hadamard designs, Witt designs

• Unary operations: complement, contraction, dual, residual

• Binary operations: sum, union

• Invariants for an incidence structure: point degrees, block degrees, covalence

• Invariants for a design: replication number, order, covalence, intersection numbers, Pascal triangle

• Properties: balanced, complete, uniform, self-dual, simple, Steiner

• Near-linear space operations: connection number, point and line regularity, restriction

• Resolutions, parallelisms, parallel classes

• Graphs and codes from designs: block graph, incidence graph, point graph, linear code

• Automorphism group (J. Leon's algorithm), isomorphism testing

• Group actions on a design: orbits and stabilizers of points and blocks

• Symmetry properties: point transitive, block transitive

Tools are provided for constructing designs from difference sets, Hadamard matrices, codes and other designs. The standard families of difference sets are incorporated. A major feature is the ability to compute automorphism groups and to test pairs of incidence structures for isomorphism.

15.7 Finite Planes

Although finite planes correspond to particular families of designs, separate categories are provided for both projective and affine planes in order to exploit the rich structure possessed by these objects.

• Creation of classical and non-classical finite projective and affine planes

• Subplanes, dual of a projective plane

• Numerical invariants: order, p-rank

• Properties: Desarguesian, self-dual

• Parallel classes of an affine plane

• k-arcs: testing, complete, tangents, secants, passants

• Conics: through given points, knot, exterior, interior

• Unitals: testing, tangents, feet

• Affine to projective planes and vice versa

• Related structures: design, incidence matrix, incidence graph, linear code

• Collineation group, isomorphism testing (optimized algorithm for projective planes)

• Central collineations: testing, groups

• Group actions on a plane: orbits and stabilizers of points and lines

• Symmetry properties: point transitive, line transitive

Apart from elementary invariants, a reasonably fast method is available for testing whether a plane is desarguesian. Among special configurations of interest, a search procedure for k-arcs is provided. A specialized algorithm developed by Jeff Leon is used to compute the collineation group of a projective plane while the affine case is handled by the incidence structure method. The collineation group (order 2³ 3⁸) of a "random" projective plane of order 81 supplied by Gordon Royle was found in 1 202 seconds. As with graphs and designs the G-set mechanism gives the action of the collineation group on any appropriate set.

15.8 Incidence Geometry

Magma 2.14 contains facilities for creating and computing with incidence geometries and coset geometries. These have been developed by Dimitri Leemans (Brussels).

The Magma Incidence Structure type comprises a set of points and a set of blocks together with an incidence relation. Following Bekenhout, we define a more general object as follows: An incidence geometry is a 4-tuple Γ = (X,*,t,I) where

• X is a set of elements;

• I is a non-empty set whose elements are called types;

• t : X→I : x ↦ t(x) is a type function which maps an element to its type;

• * is an incidence relation that is a reflexive and symmetric relation such that ∀x,y∈X, x*y and t(x)*t(y) ⇒ x = y.

We also introduce group-geometry pairs or coset geometries. Roughly speaking, these are geometries constructed from a group and some of its subgroups in the following way. Let I be a finite set and let G be a group together with a finite family of subgroups (G_i)_i∈I. We define the incidence geometry Γ = Γ(G, (G_i)_i∈I) as follows. The set X of elements or varieties of Γ consists of all cosets gG_i, g∈G, i∈I. We define an incidence relation * on X by:

Γ(G, (G_i)_i∈I) may also be called a group-geometry pair.