This section is concerned with those topics in classical Combinatorial Theory that are supported by Magma. These include:-
Enumerative combinatorics
Partitions and tableaux
Graphs—directed and undirected
Networks
Incidence structures
Designs
Other topices closely related to Combinatorial Theory, that are included in Magma, are Finite Fields, Finite Geometry, and Coding Theory. Descriptions for the facilities for these areas will be found in other sections.
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)
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
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 five 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 five bases to any other of the five bases
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
Maximum matching 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 the section on Networks below).
A multigraph is a graph which may contain loops or multiple (parallel) edges between the same pair of vertices. Vertices and edges in a multigraph may be labelled, and edges may also have associated capacities or weights, to assist flow-based or shortest-path based algorithsm. Multigraphs are represented by means of an adjacency list. Much of the same machinery is available for simple graphs and for multigraphs.
Directed and undirected multigraphs
Optional vertex and edge labels, capacities, weights
Conversion to and from simple graphs
Operations: union, join, product, contraction, etc.
Properties: bipartite, regular, connected, biconnected
Triconnectivity
General vertex and edge connectivity
Maximum matching in bipartite graphs
Spanning trees, cut-vertices, shortest paths
Planarity testing, obstruction isolation, faces, embedding
See the section on Graphs (above) for comments on some of the algorithms.
A network is a multidigraph whose edges are associated with a capacity. It may have multiple (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].
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.
Hadamard matrices are square matrices whose entries are all ±1, such that any two rows (or columns) are orthogonal. They have some useful special properties; in particular, they lead to certain classes of design; produce a family of error-correcting codes that can correct many errors; and have several important applications in signal processing.
Checking of the Hadamard property
Normalised form, simple invariant testing (4-profile)
Canonical form, equivalence testing
Construction of 3-designs from rows or columns
Automorphism group
Database of Hadamard and skew Hadamard matrices; an interface for augmenting this database with new matrices is provided
The problem of determining if two Hadamard matrices are equivalent is a difficult one. The computation of a canonical form (due to Brendan McKay's program nauty [McK81]) is one way to achieve this; Magma also contains an older algorithm of Jeff Leon that performs this equivalence testing.
Optional databases of Hadamard and skew Hadamard matrices are available. The former contains 5 391 examples of inequivalent Hadamard matrices for all possible degrees up to 256 (the degree must be 1, 2, or a multiple of four), and is a complete listing for degree up to 28. The skew Hadamard database contains 638 inequivalent skew Hadamard matrices of degree 36, 44, or 52.