Incidence structures.

An incidence structure is specified by a list of points, blocks, and an incidence matrix ([1], [2]).

REFERENCES:

[1]Block designs and incidence structures from wikipedia, Wikipedia article Block_design Wikipedia article Incidence_structure
[2]
  1. Assmus, J. Key, Designs and their codes, CUP, 1992.

AUTHORS:

  • Peter Dobcsanyi and David Joyner (2007-2008)

    This is a significantly modified form of part of the module block_design.py (version 0.6) written by Peter Dobcsanyi peter@designtheory.org.

Classes and methods

class sage.combinat.designs.incidence_structures.IncidenceStructure(pts, blks, inc_mat=None, name=None, test=True)

Bases: object

This the base class for block designs.

automorphism_group()

Returns the subgroup of the automorphism group of the incidence graph which respects the P B partition. It is (isomorphic to) the automorphism group of the block design, although the degrees differ.

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: G = BD.automorphism_group(); G
Permutation Group with generators [(4,5)(6,7), (4,6)(5,7), (2,3)(6,7), (2,4)(3,5), (1,2)(5,6)]
sage: BD = BlockDesign(4,[[0],[0,1],[1,2],[3,3]],test=False)
sage: G = BD.automorphism_group(); G
Permutation Group with generators [()]
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: G = BD.automorphism_group(); G
Permutation Group with generators [(4,5)(6,7), (4,6)(5,7), (2,3)(6,7), (2,4)(3,5), (1,2)(5,6)]
block_design_checker(t, v, k, lmbda, type=None)

This is not a wrapper for GAP Design’s IsBlockDesign. The GAP Design function IsBlockDesign http://www.gap-system.org/Manuals/pkg/design/htm/CHAP004.htm apparently simply checks the record structure and no mathematical properties. Instead, the function below checks some necessary (but not sufficient) “easy” identities arising from the identity.

INPUT:

  • t - the t as in “t-design”
  • v - the number of points
  • k - the number of blocks incident to a point
  • lmbda - each t-tuple of points should be incident with lmbda blocks
  • type - can be ‘simple’ or ‘binary’ or ‘connected’ Depending on the option, this wraps IsBinaryBlockDesign, IsSimpleBlockDesign, or IsConnectedBlockDesign.
    • Binary: no block has a repeated element.
    • Simple: no block is repeated.
    • Connected: its incidence graph is a connected graph.

WARNING: This is very fast but can return false positives.

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: BD.parameters()
(2, 7, 3, 1)
sage: BD.block_design_checker(2, 7, 3, 1)
True
sage: BD.block_design_checker(2, 7, 3, 1,"binary")
True
sage: BD.block_design_checker(2, 7, 3, 1,"connected")
True
sage: BD.block_design_checker(2, 7, 3, 1,"simple")
True
block_sizes()

Return a list of block’s sizes.

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: BD.block_sizes()
[3, 3, 3, 3, 3, 3, 3]
blocks()

Return the list of blocks.

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: BD.blocks()
[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]]
dual_design(algorithm=None)

Wraps GAP Design’s DualBlockDesign (see [1]). The dual of a block design may not be a block design.

Also can be called with dual_design.

The algorithm=”gap” option requires GAP’s Design package (included in the gap_packages Sage spkg).

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: D = BlockDesign(4, [[0,2],[1,2,3],[2,3]], test=False)
sage: D
Incidence structure with 4 points and 3 blocks
sage: D.dual_design()
Incidence structure with 3 points and 4 blocks
sage: print D.dual_design(algorithm="gap")       # optional - gap_design
IncidenceStructure<points=[0, 1, 2], blocks=[[0], [0, 1, 2], [1], [1, 2]]>
sage: BD = IncidenceStructure(range(7),[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]], name="FanoPlane")
sage: BD
Incidence structure with 7 points and 7 blocks
sage: print BD.dual_design(algorithm="gap")         # optional - gap_design
IncidenceStructure<points=[0, 1, 2, 3, 4, 5, 6], blocks=[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]]>
sage: BD.dual_incidence_structure()
Incidence structure with 7 points and 7 blocks

REFERENCE:

dual_incidence_structure(algorithm=None)

Wraps GAP Design’s DualBlockDesign (see [1]). The dual of a block design may not be a block design.

Also can be called with dual_design.

The algorithm=”gap” option requires GAP’s Design package (included in the gap_packages Sage spkg).

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: D = BlockDesign(4, [[0,2],[1,2,3],[2,3]], test=False)
sage: D
Incidence structure with 4 points and 3 blocks
sage: D.dual_design()
Incidence structure with 3 points and 4 blocks
sage: print D.dual_design(algorithm="gap")       # optional - gap_design
IncidenceStructure<points=[0, 1, 2], blocks=[[0], [0, 1, 2], [1], [1, 2]]>
sage: BD = IncidenceStructure(range(7),[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]], name="FanoPlane")
sage: BD
Incidence structure with 7 points and 7 blocks
sage: print BD.dual_design(algorithm="gap")         # optional - gap_design
IncidenceStructure<points=[0, 1, 2, 3, 4, 5, 6], blocks=[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]]>
sage: BD.dual_incidence_structure()
Incidence structure with 7 points and 7 blocks

REFERENCE:

incidence_graph()

Returns the incidence graph of the design, where the incidence matrix of the design is the adjacency matrix of the graph.

EXAMPLE:

sage: BD = IncidenceStructure(range(7),[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: BD.incidence_graph()
Bipartite graph on 14 vertices
sage: A = BD.incidence_matrix()
sage: Graph(block_matrix([[A*0,A],[A.transpose(),A*0]])) == BD.incidence_graph()
True

REFERENCE:

  • Sage Reference Manual on Graphs
incidence_matrix()

Return the incidence matrix \(A\) of the design. A is a \((v imes b)\) matrix defined by: A[i,j] = 1 if i is in block B_j and 0 otherwise.

EXAMPLES:

sage: BD = IncidenceStructure(range(7),[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: BD.block_sizes()
[3, 3, 3, 3, 3, 3, 3]
sage: BD.incidence_matrix()
[1 1 1 0 0 0 0]
[1 0 0 1 1 0 0]
[1 0 0 0 0 1 1]
[0 1 0 1 0 1 0]
[0 1 0 0 1 0 1]
[0 0 1 1 0 0 1]
[0 0 1 0 1 1 0]
is_block_design()

Returns a pair True, pars if the incidence structure is a \(t\)-design, for some \(t\), where pars is the list of parameters \((t, v, k, lmbda)\). The largest possible \(t\) is returned, provided \(t=10\).

EXAMPLES:

sage: BD = IncidenceStructure(range(7),[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: BD.is_block_design()
(True, [2, 7, 3, 1])
sage: BD.block_design_checker(2, 7, 3, 1)
True
sage: BD = designs.WittDesign(9)   # optional - gap_packages (design package)
sage: BD.is_block_design()         # optional - gap_packages (design package)
(True, [2, 9, 3, 1])
sage: BD = designs.WittDesign(12)  # optional - gap_packages (design package)
sage: BD.is_block_design()         # optional - gap_packages (design package)
(True, [5, 12, 6, 1])
sage: BD = designs.AffineGeometryDesign(3, 1, GF(2))
sage: BD.is_block_design()
(True, [2, 8, 2, 1])
parameters(t=2)

Returns \((t,v,k,lambda)\). Does not check if the input is a block design. Uses \(t=2\) by default.

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]], name="FanoPlane")
sage: BD.parameters()
(2, 7, 3, 1)
sage: BD.parameters(t=3)
(3, 7, 3, 0)
points()

Returns the list of points.

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: BD.points()
[0, 1, 2, 3, 4, 5, 6]
points_from_gap()

Literally pushes this block design over to GAP and returns the points of that. Other than debugging, usefulness is unclear.

REQUIRES: GAP’s Design package.

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: BD.points_from_gap()      # optional - gap_packages (design package)
doctest:1: DeprecationWarning: Unless somebody protests this method will be removed, as nobody seems to know why it is there.
See http://trac.sagemath.org/14499 for details.
[1, 2, 3, 4, 5, 6, 7]
sage.combinat.designs.incidence_structures.IncidenceStructureFromMatrix(M, name=None)

Builds and incidence structure from a matrix.

INPUT:

  • M – a binary matrix. Creates a set of “points” from the rows and a set of “blocks” from the columns.

EXAMPLES:

sage: from sage.combinat.designs.block_design import BlockDesign
sage: BD1 = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: M = BD1.incidence_matrix()
sage: BD2 = IncidenceStructureFromMatrix(M)
sage: BD1 == BD2
True
sage.combinat.designs.incidence_structures.coordinatewise_product(L)

Returns the coordinatewise product of a list of vectors.

INPUT:

  • L is a list of \(n\)-vectors or lists all of length \(n\) with a common parent. This returns the vector whose \(i\)-th coordinate is the product of the \(i\)-th coordinates of the vectors.

EXAMPLES:

sage: from sage.combinat.designs.incidence_structures import coordinatewise_product
sage: L = [[1,2,3],[-1,-1,-1],[5,7,11]]
sage: coordinatewise_product(L)
[-5, -14, -33]

Table Of Contents

Previous topic

External Representations of Block Designs

Next topic

Steiner Quadruple Systems

This Page