Using G & G with Combinatorial Designs and Geometries
Last update=31 January, 2000
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 SetsTo 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 GraphsUse the arrow tool to select the vertices corresponding to the blocks of a design. Then execute the Neighbour Graph command.
The Leave of a DesignTo 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 BlocksTo 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 SquaresAn nxn latin square can be represented by a graph. Create a bipartite graph K(n,n). It contains n2 edges, which will correspond to the n2 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 n2 new vertices of degree 2. Call them ij, where i,j=1..n. Create n more vertices to represent the entries (a1..an). If entry k is contained in cell ij, then join vertex ak to vertex ij. The result is a graph with n2+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 ak.
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 ak. Now create n more vertices to represent the next set of n entries. Call then bk. Join bk similarly to ak. Do the same for any additional squares. The result is a graph whose automorphism group contains all the symmetries of the MOLS.
Residual DesignsSelect 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 DesignsSelect 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.
Back to the Groups & Graphs home page.