# 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] 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]