An incidence structure is specified by a list of points, blocks, or an incidence matrix ([1], [2]). IncidenceStructure instances have the following methods:
ground_set()  Return the ground set (i.e the list of points). 
num_points()  Return the size of the ground set. 
num_blocks()  Return the number of blocks. 
blocks()  Return the list of blocks. 
block_sizes()  Return the set of block sizes. 
degree()  Return the degree of a point \(p\) 
degrees()  Return the degree of all sets of given size, or the degree of all points. 
is_connected()  Test whether the design is connected. 
is_simple()  Test whether this design is simple (i.e. no repeated block). 
incidence_matrix()  Return the incidence matrix \(A\) of the design 
incidence_graph()  Return the incidence graph of the design 
packing()  Return a maximum packing 
relabel()  Relabel the ground set 
is_resolvable()  Test whether the hypergraph is resolvable 
is_t_design()  Test whether self is a \(t(v,k,l)\) design. 
dual()  Return the dual design. 
automorphism_group()  Return the automorphism group 
canonical_label()  Return a canonical label for the incidence structure. 
is_isomorphic()  Return whether the two incidence structures are isomorphic. 
edge_coloring()  Return an optimal edge coloring` 
copy()  Return a copy of the incidence structure. 
induced_substructure()  Return the substructure induced by a set of points. 
trace()  Return the trace of a set of point 
REFERENCES:
[1]  Block designs and incidence structures from wikipedia, Wikipedia article Block_design Wikipedia article Incidence_structure 
[2] 

AUTHORS:
Peter Dobcsanyi and David Joyner (20072008)
This is a significantly modified form of part of the module block_design.py (version 0.6) written by Peter Dobcsanyi peter@designtheory.org.
Vincent Delecroix (2014): major rewrite
Bases: object
A base class for incidence structures (i.e. hypergraphs, i.e. set systems)
An incidence structure (i.e. hypergraph, i.e. set system) can be defined from a collection of blocks (i.e. sets, i.e. edges), optionally with an explicit ground set (i.e. point set, i.e. vertex set). Alternatively they can be defined from a binary incidence matrix.
INPUT:
points – (i.e. ground set, i.e. vertex set) the underlying set. If points is an integer \(v\), then the set is considered to be \(\{0, ..., v1\}\).
Note
The following syntax, where points is ommitted, automatically defines the ground set as the union of the blocks:
sage: H = IncidenceStructure([['a','b','c'],['c','d','e']])
sage: H.ground_set()
['a', 'b', 'c', 'd', 'e']
blocks – (i.e. edges, i.e. sets) the blocks defining the incidence structure. Can be any iterable.
incidence_matrix – a binary incidence matrix. Each column represents a set.
name (a string, such as “Fano plane”).
check – whether to check the input
copy – (use with caution) if set to False then blocks must be a list of lists of integers. The list will not be copied but will be modified in place (each block is sorted, and the whole list is sorted). Your blocks object will become the IncidenceStructure instance’s internal data.
EXAMPLES:
An incidence structure can be constructed by giving the number of points and the list of blocks:
sage: designs.IncidenceStructure(7, [[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
Incidence structure with 7 points and 7 blocks
Only providing the set of blocks is sufficient. In this case, the ground set is defined as the union of the blocks:
sage: IncidenceStructure([[1,2,3],[2,3,4]])
Incidence structure with 4 points and 2 blocks
Or by its adjacency matrix (a \(\{0,1\}\)matrix in which rows are indexed by points and columns by blocks):
sage: m = matrix([[0,1,0],[0,0,1],[1,0,1],[1,1,1]])
sage: designs.IncidenceStructure(m)
Incidence structure with 4 points and 3 blocks
The points can be any (hashable) object:
sage: V = [(0,'a'),(0,'b'),(1,'a'),(1,'b')]
sage: B = [(V[0],V[1],V[2]), (V[1],V[2]), (V[0],V[2])]
sage: I = designs.IncidenceStructure(V, B)
sage: I.ground_set()
[(0, 'a'), (0, 'b'), (1, 'a'), (1, 'b')]
sage: I.blocks()
[[(0, 'a'), (0, 'b'), (1, 'a')], [(0, 'a'), (1, 'a')], [(0, 'b'), (1, 'a')]]
The order of the points and blocks does not matter as they are sorted on input (see trac ticket #11333):
sage: A = designs.IncidenceStructure([0,1,2], [[0],[0,2]])
sage: B = designs.IncidenceStructure([1,0,2], [[0],[2,0]])
sage: B == A
True
sage: C = designs.BlockDesign(2, [[0], [1,0]])
sage: D = designs.BlockDesign(2, [[0,1], [0]])
sage: C == D
True
If you care for speed, you can set copy to False, but in that case, your input must be a list of lists and the ground set must be \({0, ..., v1}\):
sage: blocks = [[0,1],[2,0],[1,2]] # a list of lists of integers
sage: I = designs.IncidenceStructure(3, blocks, copy=False)
sage: I._blocks is blocks
True
Return 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: P = designs.DesarguesianProjectivePlaneDesign(2); P
Incidence structure with 7 points and 7 blocks
sage: G = P.automorphism_group()
sage: G.is_isomorphic(PGL(3,2))
True
sage: G
Permutation Group with generators [(2,3)(4,5), (2,4)(3,5), (1,2)(4,6), (0,1)(4,5)]
A non selfdual example:
sage: IS = designs.IncidenceStructure(range(4), [[0,1,2,3],[1,2,3]])
sage: IS.automorphism_group().cardinality()
6
sage: IS.dual().automorphism_group().cardinality()
1
Examples with noninteger points:
sage: I = designs.IncidenceStructure('abc', ('ab','ac','bc'))
sage: I.automorphism_group()
Permutation Group with generators [('b','c'), ('a','b')]
sage: designs.IncidenceStructure([[(1,2),(3,4)]]).automorphism_group()
Permutation Group with generators [((1,2),(3,4))]
This method is deprecated and will soon be removed (see trac ticket #16553). You could use is_t_design() instead.
This is not a wrapper for GAP Design’s IsBlockDesign. The GAP Design function IsBlockDesign http://www.gapsystem.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:
WARNING: This is very fast but can return false positives.
EXAMPLES:
sage: BD = designs.IncidenceStructure(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_t_design(return_parameters=True)
(True, (2, 7, 3, 1))
sage: BD.block_design_checker(2, 7, 3, 1)
doctest:...: DeprecationWarning: .block_design_checker(v,t,k,lmbda) is deprecated; please use
.is_t_design(v,t,k,lmbda) instead
See http://trac.sagemath.org/16553 for details.
True
sage: BD.block_design_checker(2, 7, 3, 1,"binary")
doctest:...: DeprecationWarning: .block_design_checker(type='binary') is
deprecated; use .is_binary() instead
See http://trac.sagemath.org/16553 for details.
True
sage: BD.block_design_checker(2, 7, 3, 1,"connected")
doctest:...: DeprecationWarning: block_design_checker(type='connected') is
deprecated, please use .is_connected() instead
See http://trac.sagemath.org/16553 for details.
True
sage: BD.block_design_checker(2, 7, 3, 1,"simple")
doctest:...: DeprecationWarning: .block_design_checker(type='simple')
is deprecated; all designs here are simple!
See http://trac.sagemath.org/16553 for details.
True
Return the set of block sizes.
EXAMPLES:
sage: BD = designs.IncidenceStructure(8, [[0,1,3],[1,4,5,6],[1,2],[5,6,7]])
sage: BD.block_sizes()
[3, 2, 4, 3]
sage: BD = designs.IncidenceStructure(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]
Return the list of blocks.
EXAMPLES:
sage: BD = designs.IncidenceStructure(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]]
Return a canonical label for the incidence structure.
A canonical label is relabeling of the points into integers \(\{0,...,n1\}\) such that isomorphic incidence structures are relabelled to equal objects.
EXAMPLE:
sage: fano1 = designs.balanced_incomplete_block_design(7,3)
sage: fano2 = designs.projective_plane(2)
sage: fano1 == fano2
False
sage: fano1.relabel(fano1.canonical_label())
sage: fano2.relabel(fano2.canonical_label())
sage: fano1 == fano2
True
Return a copy of the incidence structure.
EXAMPLE:
sage: IS = IncidenceStructure([[1,2,3,"e"]],name="Test")
sage: IS
Incidence structure with 4 points and 1 blocks
sage: copy(IS)
Incidence structure with 4 points and 1 blocks
sage: [1, 2, 3, 'e'] in copy(IS)
True
sage: copy(IS)._name
'Test'
Return the degree of a point p (or a set of points).
The degree of a point (or set of points) is the number of blocks that contain it.
INPUT:
EXAMPLES:
sage: designs.steiner_triple_system(9).degree(3)
4
sage: designs.steiner_triple_system(9).degree({1,2},subset=True)
1
TESTS:
sage: designs.steiner_triple_system(9).degree()
doctest:...: DeprecationWarning: Please use degrees() instead of degree(None)
See http://trac.sagemath.org/17108 for details.
{0: 4, 1: 4, 2: 4, 3: 4, 4: 4, 5: 4, 6: 4, 7: 4, 8: 4}
sage: designs.steiner_triple_system(9).degree(subset=True)
Traceback (most recent call last):
...
ValueError: subset must be False when p is None
Return the degree of all sets of given size, or the degree of all points.
The degree of a point (or set of point) is the number of blocks that contain it.
INPUT:
size (integer) – return the degree of all subsets of points of cardinality size. When size=None, the function outputs the degree of all points.
Note
When size=None the output is indexed by the points. When size=1 it is indexed by tuples of size 1. This is the same information, stored slightly differently.
OUTPUT:
A dictionary whose values are degrees and keys are either:
EXAMPLES:
sage: IncidenceStructure([[1,2,3],[1,4]]).degrees(2)
{(1, 2): 1, (1, 3): 1, (1, 4): 1, (2, 3): 1, (2, 4): 0, (3, 4): 0}
In a steiner triple system, all pairs have degree 1:
sage: S13 = designs.steiner_triple_system(13)
sage: all(v == 1 for v in S13.degrees(2).itervalues())
True
Return the dual of the incidence structure.
INPUT:
algorithm – whether to use Sage’s implementation (algorithm=None, default) or use GAP’s (algorithm="gap").
Note
The algorithm="gap" option requires GAP’s Design package (included in the gap_packages Sage spkg).
EXAMPLES:
The dual of a projective plane is a projective plane:
sage: PP = designs.DesarguesianProjectivePlaneDesign(4)
sage: PP.dual().is_t_design(return_parameters=True)
(True, (2, 21, 5, 1))
TESTS:
sage: D = designs.IncidenceStructure(4, [[0,2],[1,2,3],[2,3]])
sage: D
Incidence structure with 4 points and 3 blocks
sage: D.dual()
Incidence structure with 3 points and 4 blocks
sage: print D.dual(algorithm="gap") # optional  gap_packages
IncidenceStructure<points=[0, 1, 2], blocks=[[0], [0, 1, 2], [1], [1, 2]]>
sage: blocks = [[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]]
sage: BD = designs.IncidenceStructure(7, blocks, name="FanoPlane");
sage: BD
Incidence structure with 7 points and 7 blocks
sage: print BD.dual(algorithm="gap") # optional  gap_packages
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 with 7 points and 7 blocks
REFERENCE:
Deprecated: Use dual() instead. See trac ticket #16553 for details.
Deprecated: Use dual() instead. See trac ticket #16553 for details.
Compute a proper edgecoloring.
A proper edgecoloring is an assignment of colors to the sets of the incidence structure such that two sets with nonempty intersection receive different colors. The coloring returned minimizes the number of colors.
OUTPUT:
A partition of the sets into color classes.
EXAMPLES:
sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{4,5,6}]); H
Incidence structure with 6 points and 4 blocks
sage: C = H.edge_coloring()
sage: C # random
[[[3, 4, 5]], [[2, 3, 4]], [[4, 5, 6], [1, 2, 3]]]
sage: Set(map(Set,sum(C,[]))) == Set(map(Set,H.blocks()))
True
Return the ground set (i.e the list of points).
EXAMPLES:
sage: designs.IncidenceStructure(3, [[0,1],[0,2]]).ground_set()
[0, 1, 2]
Return the incidence graph of the design, where the incidence matrix of the design is the adjacency matrix of the graph.
EXAMPLE:
sage: BD = designs.IncidenceStructure(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:
Return the incidence matrix \(A\) of the design. A is a \((v \times b)\) matrix defined by: A[i,j] = 1 if i is in block B_j and 0 otherwise.
EXAMPLES:
sage: BD = designs.IncidenceStructure(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]
sage: I = designs.IncidenceStructure('abc', ('ab','abc','ac','c'))
sage: I.incidence_matrix()
[1 1 1 0]
[1 1 0 0]
[0 1 1 1]
Return the substructure induced by a set of points.
The substructure induced in \(\mathcal H\) by a set \(X\subseteq V(\mathcal H)\) of points is the incidence structure \(\mathcal H_X\) defined on \(X\) whose sets are all \(S\in \mathcal H\) such that \(S\subseteq X\).
INPUT:
Note
This method goes over all sets of self before building a new IncidenceStructure (which involves some relabelling and sorting). It probably should not be called in a performancecritical code.
EXAMPLE:
A Fano plane with one point removed:
sage: F = designs.steiner_triple_system(7)
sage: F.induced_substructure([0..5])
Incidence structure with 6 points and 4 blocks
TESTS:
sage: F.induced_substructure([0..50])
Traceback (most recent call last):
...
ValueError: 7 is not a point of the incidence structure
sage: F.relabel(dict(enumerate("abcdefg")))
sage: F.induced_substructure("abc")
Incidence structure with 3 points and ...
sage: F.induced_substructure("Y")
Traceback (most recent call last):
...
ValueError: 'Y' is not a point of the incidence structure
Deprecated: Use is_t_design() instead. See trac ticket #16553 for details.
Test whether the design is connected.
EXAMPLES:
sage: designs.IncidenceStructure(3, [[0,1],[0,2]]).is_connected()
True
sage: designs.IncidenceStructure(4, [[0,1],[2,3]]).is_connected()
False
Return whether the two incidence structures are isomorphic.
Note
If you need to test isomorphisms between one incidence structure and many others, you should consider using canonical_label() instead of this function.
INPUT:
EXAMPLE:
sage: fano1 = designs.balanced_incomplete_block_design(7,3)
sage: fano2 = designs.projective_plane(2)
sage: fano1.is_isomorphic(fano2)
True
sage: fano1.is_isomorphic(fano2,certificate=True)
{0: 0, 1: 1, 2: 2, 3: 6, 4: 4, 5: 3, 6: 5}
TESTS:
sage: IS = IncidenceStructure([["A",5,pi],["A",5,"Wouhou"],["A","Wouhou",(9,9)],[pi,12]])
sage: IS2 = IS.copy()
sage: IS2.relabel(IS2.canonical_label())
sage: IS.is_isomorphic(IS2)
True
sage: canon = IS.is_isomorphic(IS2,certificate=True)
sage: IS.relabel(canon)
sage: IS==IS2
True
sage: IS2 = IncidenceStructure([[1,2]])
sage: IS2.is_isomorphic(IS)
False
sage: IS2.is_isomorphic(IS,certificate=True)
{}
Test whether the hypergraph is resolvable
A hypergraph is said to be resolvable if its sets can be partitionned into classes, each of which is a partition of the ground set.
Note
This problem is solved using an Integer Linear Program, and GLPK (the default LP solver) has been reported to be very slow on some instances. If you hit this wall, consider installing a more powerful LP solver (CPLEX, Gurobi, ...).
INPUT:
EXAMPLES:
Some resolvable designs:
sage: TD = designs.transversal_design(2,2,resolvable=True)
sage: TD.is_resolvable()
True
sage: AG = designs.AffineGeometryDesign(3,1,GF(2))
sage: AG.is_resolvable()
True
Their classes:
sage: b,cls = TD.is_resolvable(True)
sage: b
True
sage: cls # random
[[[0, 3], [1, 2]], [[1, 3], [0, 2]]]
sage: b,cls = AG.is_resolvable(True)
sage: b
True
sage: cls # random
[[[6, 7], [4, 5], [0, 1], [2, 3]],
[[5, 7], [0, 4], [3, 6], [1, 2]],
[[0, 2], [4, 7], [1, 3], [5, 6]],
[[3, 4], [0, 7], [1, 5], [2, 6]],
[[3, 7], [1, 6], [0, 5], [2, 4]],
[[0, 6], [2, 7], [1, 4], [3, 5]],
[[4, 6], [0, 3], [2, 5], [1, 7]]]
A nonresolvable design:
sage: Fano = designs.balanced_incomplete_block_design(7,3)
sage: Fano.is_resolvable()
False
sage: Fano.is_resolvable(True)
(False, [])
TESTS:
sage: _,cls1 = AG.is_resolvable(certificate=True)
sage: _,cls2 = AG.is_resolvable(certificate=True)
sage: cls1 is cls2
False
Test whether this design is simple (i.e. no repeated block).
EXAMPLES:
sage: designs.IncidenceStructure(3, [[0,1],[1,2],[0,2]]).is_simple()
True
sage: designs.IncidenceStructure(3, [[0],[0]]).is_simple()
False
sage: V = [(0,'a'),(0,'b'),(1,'a'),(1,'b')]
sage: B = [[V[0],V[1]], [V[1],V[2]]]
sage: I = designs.IncidenceStructure(V, B)
sage: I.is_simple()
True
sage: I2 = designs.IncidenceStructure(V, B*2)
sage: I2.is_simple()
False
Test whether self is a \(t(v,k,l)\) design.
A \(t(v,k,\lambda)\) (sometimes called \(t\)design for short) is a block design in which:
INPUT:
EXAMPLES:
sage: fano_blocks = [[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]]
sage: BD = designs.IncidenceStructure(7, fano_blocks)
sage: BD.is_t_design()
True
sage: BD.is_t_design(return_parameters=True)
(True, (2, 7, 3, 1))
sage: BD.is_t_design(2, 7, 3, 1)
True
sage: BD.is_t_design(1, 7, 3, 3)
True
sage: BD.is_t_design(0, 7, 3, 7)
True
sage: BD.is_t_design(0,6,3,7) or BD.is_t_design(0,7,4,7) or BD.is_t_design(0,7,3,8)
False
sage: BD = designs.AffineGeometryDesign(3, 1, GF(2))
sage: BD.is_t_design(1)
True
sage: BD.is_t_design(2)
True
Steiner triple and quadruple systems are other names for \(2(v,3,1)\) and \(3(v,4,1)\) designs:
sage: S3_9 = designs.steiner_triple_system(9)
sage: S3_9.is_t_design(2,9,3,1)
True
sage: blocks = designs.steiner_quadruple_system(8)
sage: S4_8 = designs.IncidenceStructure(8, blocks)
sage: S4_8.is_t_design(3,8,4,1)
True
sage: blocks = designs.steiner_quadruple_system(14)
sage: S4_14 = designs.IncidenceStructure(14, blocks)
sage: S4_14.is_t_design(3,14,4,1)
True
Some examples of Witt designs that need the gap database:
sage: BD = designs.WittDesign(9) # optional  gap_packages
sage: BD.is_t_design(2,9,3,1) # optional  gap_packages
True
sage: W12 = designs.WittDesign(12) # optional  gap_packages
sage: W12.is_t_design(5,12,6,1) # optional  gap_packages
True
sage: W12.is_t_design(4) # optional  gap_packages
True
Further examples:
sage: D = designs.IncidenceStructure(4,[[],[]])
sage: D.is_t_design(return_parameters=True)
(True, (0, 4, 0, 2))
sage: D = designs.IncidenceStructure(4, [[0,1],[0,2],[0,3]])
sage: D.is_t_design(return_parameters=True)
(True, (0, 4, 2, 3))
sage: D = designs.IncidenceStructure(4, [[0],[1],[2],[3]])
sage: D.is_t_design(return_parameters=True)
(True, (1, 4, 1, 1))
sage: D = designs.IncidenceStructure(4,[[0,1],[2,3]])
sage: D.is_t_design(return_parameters=True)
(True, (1, 4, 2, 1))
sage: D = designs.IncidenceStructure(4, [range(4)])
sage: D.is_t_design(return_parameters=True)
(True, (4, 4, 4, 1))
TESTS:
sage: blocks = designs.steiner_quadruple_system(8)
sage: S4_8 = designs.IncidenceStructure(8, blocks)
sage: R = range(15)
sage: [(v,k,l) for v in R for k in R for l in R if S4_8.is_t_design(3,v,k,l)]
[(8, 4, 1)]
sage: [(v,k,l) for v in R for k in R for l in R if S4_8.is_t_design(2,v,k,l)]
[(8, 4, 3)]
sage: [(v,k,l) for v in R for k in R for l in R if S4_8.is_t_design(1,v,k,l)]
[(8, 4, 7)]
sage: [(v,k,l) for v in R for k in R for l in R if S4_8.is_t_design(0,v,k,l)]
[(8, 4, 14)]
sage: A = designs.AffineGeometryDesign(3, 1, GF(2))
sage: A.is_t_design(return_parameters=True)
(True, (2, 8, 2, 1))
sage: A = designs.AffineGeometryDesign(4, 2, GF(2))
sage: A.is_t_design(return_parameters=True)
(True, (3, 16, 4, 1))
sage: I = designs.IncidenceStructure(2, [])
sage: I.is_t_design(return_parameters=True)
(True, (0, 2, 0, 0))
sage: I = designs.IncidenceStructure(2, [[0],[0,1]])
sage: I.is_t_design(return_parameters=True)
(False, (0, 0, 0, 0))
Return the number of blocks.
EXAMPLES:
sage: designs.DesarguesianProjectivePlaneDesign(2).num_blocks()
7
sage: B = designs.IncidenceStructure(4, [[0,1],[0,2],[0,3],[1,2], [1,2,3]])
sage: B.num_blocks()
5
Return the size of the ground set.
EXAMPLES:
sage: designs.DesarguesianProjectivePlaneDesign(2).num_points()
7
sage: B = designs.IncidenceStructure(4, [[0,1],[0,2],[0,3],[1,2], [1,2,3]])
sage: B.num_points()
4
Return a maximum packing
A maximum packing in a hypergraph is collection of disjoint sets/blocks of maximal cardinality. This problem is NPcomplete in general, and in particular on 3uniform hypergraphs. It is solved here with an Integer Linear Program.
For more information, see the Wikipedia article Packing_in_a_hypergraph.
INPUT:
EXAMPLE:
sage; IncidenceStructure([[1,2],[3,"A"],[2,3]]).packing()
[[1, 2], [3, 'A']]
sage: len(designs.steiner_triple_system(9).packing())
3
Deprecated function. You should use is_t_design() instead.
EXAMPLES:
sage: I = designs.IncidenceStructure('abc', ['ab','ac','bc'])
sage: I.parameters()
doctest:...: DeprecationWarning: .parameters() is deprecated. Use
`is_t_design` instead
See http://trac.sagemath.org/16553 for details.
(2, 3, 2, 1)
Deprecated: Use ground_set() instead. See trac ticket #16553 for details.
Relabel the ground set
INPUT:
perm – can be one of
 a dictionary – then each point p (which should be a key of d) is relabeled to d[p]
 a list or a tuple of length n – the first point returned by ground_set() is relabeled to l[0], the second to l[1], ...
 None – the incidence structure is relabeled to be on \(\{0,1,...,n1\}\) in the ordering given by ground_set().
inplace – If True then return a relabeled graph and does not touch self (default is False).
EXAMPLES:
sage: TD=designs.transversal_design(5,5)
sage: TD.relabel({i:chr(97+i) for i in range(25)})
sage: print TD.ground_set()
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y']
sage: print TD.blocks()[:3]
[['a', 'f', 'k', 'p', 'u'], ['a', 'g', 'm', 's', 'y'], ['a', 'h', 'o', 'q', 'x']]
Relabel to integer points:
sage: TD.relabel()
sage: print TD.blocks()[:3]
[[0, 5, 10, 15, 20], [0, 6, 12, 18, 24], [0, 7, 14, 16, 23]]
TESTS:
Check that the relabel is consistent on a fixed incidence structure:
sage: I = designs.IncidenceStructure([0,1,2,3,4],
....: [[0,1,3],[0,2,4],[2,3,4],[0,1]])
sage: I.relabel()
sage: from itertools import permutations
sage: for p in permutations([0,1,2,3,4]):
....: J = I.relabel(p,inplace=False)
....: if I == J: print p
(0, 1, 2, 3, 4)
(0, 1, 4, 3, 2)
And one can also verify that we have exactly two automorphisms:
sage: I.automorphism_group()
Permutation Group with generators [(2,4)]
Return the trace of a set of points.
Given an hypergraph \(\mathcal H\), the trace of a set \(X\) of points in \(\mathcal H\) is the hypergraph whose blocks are all nonempty \(S \cap X\) where \(S \in \mathcal H\).
INPUT:
Note
This method goes over all sets of self before building a new IncidenceStructure (which involves some relabelling and sorting). It probably should not be called in a performancecritical code.
EXAMPLE:
A Baer subplane of order 2 (i.e. a Fano plane) in a projective plane of order 4:
sage: P4 = designs.projective_plane(4)
sage: F = designs.projective_plane(2)
sage: for x in Subsets(P4.ground_set(),7):
....: if P4.trace(x,min_size=2).is_isomorphic(F):
....: break
sage: subplane = P4.trace(x,min_size=2); subplane
Incidence structure with 7 points and 7 blocks
sage: subplane.is_isomorphic(F)
True
TESTS:
sage: F.trace([0..50])
Traceback (most recent call last):
...
ValueError: 7 is not a point of the incidence structure
sage: F.relabel(dict(enumerate("abcdefg")))
sage: F.trace("abc")
Incidence structure with 3 points and ...
sage: F.trace("Y")
Traceback (most recent call last):
...
ValueError: 'Y' is not a point of the incidence structure
Deprecated function that builds an incidence structure from a matrix.
You should now use designs.IncidenceStructure(incidence_matrix=M).
INPUT:
EXAMPLES:
sage: BD1 = designs.IncidenceStructure(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)
doctest:...: DeprecationWarning: IncidenceStructureFromMatrix is deprecated.
Please use designs.IncidenceStructure(incidence_matrix=M) instead.
See http://trac.sagemath.org/16553 for details.
sage: BD1 == BD2
True