Combinatorial Designs

Using G & G with Combinatorial Designs and Geometries

Last update=31 January, 2000

hrule

Combinatorial designs and geometries can be represented as bipartite graphs, points versus blocks or lines. A limited ability to compute with designs is available.

Difference Sets

To build a design on n points from a difference set, first create a cyclic group on n points. Then create an emtpy graph on n points and use the sputnik tool to add a new vertex joined to the points of the difference set (eg., add a point adjacent to 1,2,4 when n=7). Then use the Symmetrize command. G & G will build the incidence graph of the design. This also works for non-abelian groups, or for more than one starting block.

Block Intersection Graphs

Use the arrow tool to select the vertices corresponding to the blocks of a design. Then execute the Neighbour Graph command.

The Leave of a Design

To find the pairs of points that do not occur together in any block, use the arrow tool to select the vertices corresponding to the points of the design. Then execute the Neighbour Graph command, and take the Complement of the result.

Complementing the Blocks

To take the complement of each block of a design, use the arrow tool to select the vertices corresponding to the points. Then execute the Switch command from the Edit menu.

Latin Squares

An nxn latin square can be represented by a graph. Create a bipartite graph K(n,n). It contains n² edges, which will correspond to the n² cells of the latin square. One side of the bipartition will correspond to the rows of the latin square. The other side will correspond to the columns. Select all the vertices and induce a subgraph. Subdivide (Subgraph Menu) all the edges of the subgraph. This will create n² new vertices of degree 2. Call them ij, where i,j=1..n. Create n more vertices to represent the entries (a₁..a_n). If entry k is contained in cell ij, then join vertex a_k to vertex ij. The result is a graph with n²+n vertices representing a latin square. Automorphisms of this graph may permute rows, columns, and entries. If rows and columns are to be distinguished from entries, add a new vertex joined to every a_k.

To represent one or more pairwise-orthogonal latin squares of side n, begin with one latin square as described above. Add a new vertex joined to all the vertices a_k. Now create n more vertices to represent the next set of n entries. Call then b_k. Join b_k similarly to a_k. Do the same for any additional squares. The result is a graph whose automorphism group contains all the symmetries of the MOLS.

Residual Designs

Select the vertex corresponding to a block B. Select "Edge Cut" from the drawing menu followed by "Select Subgraph" from the subgraph menu, to select all points in block B. Then delete these vertices. The result is the residual design corresponding to block B.

Derived Designs

Select the vertex corresponding to a block B. Select "Edge Cut" from the drawing menu followed by "Select Subgraph" from the subgraph menu, to select all points in block B. Now execute "Edge Cut" again to find all edges incident on one of these vertices. Execute "Extract Subgraph" to obtain the derived design.

hrule

Back to the Groups & Graphs home page.