Incidence structures (i.e. hypergraphs, i.e. set systems)¶
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 ![]() |
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 ![]() |
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 ![]() |
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. |
isomorphic_substructures_iterator() |
Iterates over all copies of H2 contained in self |
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 (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.
Vincent Delecroix (2014): major rewrite
Methods¶
-
class
sage.combinat.designs.incidence_structures.
IncidenceStructure
(points=None, blocks=None, incidence_matrix=None, name=None, check=True, test=None, copy=True)¶ 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. Ifpoints
is an integer, then the set is considered to be
.
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 inputcopy
– (use with caution) if set toFalse
thenblocks
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). Yourblocks
object will become theIncidenceStructure
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
-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
toFalse
, but in that case, your input must be a list of lists and the ground set must be:
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
-
automorphism_group
()¶ 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 (7,3,1)-Balanced Incomplete Block Design sage: G = P.automorphism_group() sage: G.is_isomorphic(PGL(3,2)) True sage: G Permutation Group with generators [...] sage: G.cardinality() 168
A non self-dual 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 non-integer 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))]
-
block_design_checker
(t, v, k, lmbda, type=None)¶ 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.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 pointsk
- the number of blocks incident to a pointlmbda
- each t-tuple of points should be incident with lmbda blockstype
- 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: 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
-
block_sizes
()¶ 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]
-
blocks
()¶ 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]]
-
canonical_label
()¶ Return a canonical label for the incidence structure.
A canonical label is relabeling of the points into integers
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
-
copy
()¶ 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'
-
degree
(p=None, subset=False)¶ 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:
p
– a point (or a set of points) of the incidence structure.subset
(boolean) – whether to interpret the argument as a set of point (subset=True
) or as a point (subset=False
, default).
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
-
degrees
(size=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 cardinalitysize
. Whensize=None
, the function outputs the degree of all points.Note
When
size=None
the output is indexed by the points. Whensize=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:
- the points of the incidence structure if
size=None
(default) - the subsets of size
size
of the points stored as tuples
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
-
dual
(algorithm=None)¶ 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 Incidence structure with 3 points and 4 blocks 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 Incidence structure with 7 points and 7 blocks sage: BD.dual() Incidence structure with 7 points and 7 blocks
REFERENCE:
- Soicher, Leonard, Design package manual, available at http://www.gap-system.org/Manuals/pkg/design/htm/CHAP003.htm
-
dual_design
(*args, **kwds)¶ Deprecated: Use
dual()
instead. See trac ticket #16553 for details.
-
dual_incidence_structure
(*args, **kwds)¶ Deprecated: Use
dual()
instead. See trac ticket #16553 for details.
-
edge_coloring
()¶ Compute a proper edge-coloring.
A proper edge-coloring is an assignment of colors to the sets of the incidence structure such that two sets with non-empty 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
-
ground_set
()¶ Return the ground set (i.e the list of points).
EXAMPLES:
sage: designs.IncidenceStructure(3, [[0,1],[0,2]]).ground_set() [0, 1, 2]
-
incidence_graph
()¶ 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:
- Sage Reference Manual on Graphs
-
incidence_matrix
()¶ Return the incidence matrix
of the design. A is a
matrix defined by:
A[i,j] = 1
ifi
is in blockB_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]
-
induced_substructure
(points)¶ Return the substructure induced by a set of points.
The substructure induced in
by a set
of points is the incidence structure
defined on
whose sets are all
such that
.
INPUT:
points
– a set of points.
Note
This method goes over all sets of
self
before building a newIncidenceStructure
(which involves some relabelling and sorting). It probably should not be called in a performance-critical 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
-
is_block_design
(*args, **kwds)¶ Deprecated: Use
is_t_design()
instead. See trac ticket #16553 for details.
-
is_connected
()¶ 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
-
is_isomorphic
(other, certificate=False)¶ Return whether the two incidence structures are isomorphic.
INPUT:
other
– an incidence structure.certificate
(boolean) – whether to return an insomorphism fromself
toother
instead of a boolean answer.
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) {}
Checking whether two
IncidenceStructure
are isomorphic incidentally computes their canonical label (if necessary). Thus, subsequent calls tois_isomorphic()
will be faster:sage: IS1 = designs.projective_plane(3) sage: IS2 = IS1.relabel(Permutations(IS1.ground_set()).random_element(),inplace=False) sage: IS2 = IncidenceStructure(IS2.blocks()) sage: IS1._canonical_label is None and IS2._canonical_label is None True sage: IS1.is_isomorphic(IS2) True sage: IS1._canonical_label is None or IS2._canonical_label is None False
-
is_resolvable
(certificate=False, solver=None, verbose=0, check=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:
certificate
(boolean) – whether to return the classes along with the binary answer (see examples below).solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.check
(boolean) – whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set toTrue
by default.
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 non-resolvable 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
-
is_simple
()¶ 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
-
is_t_design
(t=None, v=None, k=None, l=None, return_parameters=False)¶ Test whether
self
is adesign.
A
(sometimes called
-design for short) is a block design in which:
- the underlying set has cardinality
- the blocks have size
- each
-subset of points is covered by
blocks
INPUT:
t,v,k,l
(integers) – their value is set toNone
by default. The function tests whether the design is at-(v,k,l)
design using the provided values and guesses the others. Note thatcannot be specified if
t
is not.return_parameters
(boolean)– whether to return the parameters of the-design. If set to
True
, the function returns a pair(boolean_answer,(t,v,k,l))
.
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
and
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))
- the underlying set has cardinality
-
isomorphic_substructures_iterator
(H2, induced=False)¶ Iterates over all copies of
H2
contained inself
.A hypergraph
contains an isomorphic copy of a hypergraph
if there exists an injection
such that for any set
the set
belongs to
.
It is an induced copy if no other set of
is contained in
, i.e.
.
This function lists all such injections. In particular, the number of copies of
in itself is equal to the size of its automorphism group.
See
subhypergraph_search
for more information.INPUT:
H2
anIncidenceStructure
object.induced
(boolean) – whether to require the copies to be induced. Set toFalse
by default.
EXAMPLES:
How many distinct
in Petersen’s graph ?
sage: P = graphs.PetersenGraph() sage: C = graphs.CycleGraph(5) sage: IP = IncidenceStructure(P.edges(labels=False)) sage: IC = IncidenceStructure(C.edges(labels=False)) sage: sum(1 for _ in IP.isomorphic_substructures_iterator(IC)) 120
As the automorphism group of
has size 10, the number of distinct unlabelled copies is 12. Let us check that all functions returned correspond to an actual
subgraph:
sage: for f in IP.isomorphic_substructures_iterator(IC): ....: assert all(P.has_edge(f[x],f[y]) for x,y in C.edges(labels=False))
The number of induced copies, in this case, is the same:
sage: sum(1 for _ in IP.isomorphic_substructures_iterator(IC,induced=True)) 120
They begin to differ if we make one vertex universal:
sage: P.add_edges([(0,x) for x in P]) sage: IP = IncidenceStructure(P.edges(labels=False)) sage: IC = IncidenceStructure(C.edges(labels=False)) sage: sum(1 for _ in IP.isomorphic_substructures_iterator(IC)) 420 sage: sum(1 for _ in IP.isomorphic_substructures_iterator(IC,induced=True)) 60
The number of copies of
in itself is the size of its automorphism group:
sage: H = designs.projective_plane(3) sage: sum(1 for _ in H.isomorphic_substructures_iterator(H)) 5616 sage: H.automorphism_group().cardinality() 5616
-
num_blocks
()¶ 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
-
num_points
()¶ 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
-
packing
(solver=None, verbose=0)¶ Return a maximum packing
A maximum packing in a hypergraph is collection of disjoint sets/blocks of maximal cardinality. This problem is NP-complete in general, and in particular on 3-uniform hypergraphs. It is solved here with an Integer Linear Program.
For more information, see the Wikipedia article Packing_in_a_hypergraph.
INPUT:
solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet. Only useful whenalgorithm == "LP"
.
EXAMPLE:
sage; IncidenceStructure([[1,2],[3,"A"],[2,3]]).packing() [[1, 2], [3, 'A']] sage: len(designs.steiner_triple_system(9).packing()) 3
-
parameters
()¶ 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)
-
points
(*args, **kwds)¶ Deprecated: Use
ground_set()
instead. See trac ticket #16553 for details.
-
relabel
(perm=None, inplace=True)¶ Relabel the ground set
INPUT:
perm
– can be one of- a dictionary – then each point
p
(which should be a key ofd
) is relabeled tod[p]
- a list or a tuple of length
n
– the first point returned byground_set()
is relabeled tol[0]
, the second tol[1]
, ... None
– the incidence structure is relabeled to be onin the ordering given by
ground_set()
.
- a dictionary – then each point
inplace
– IfTrue
then return a relabeled graph and does not touchself
(default isFalse
).
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)]
-
trace
(points, min_size=1, multiset=True)¶ Return the trace of a set of points.
Given an hypergraph
, the trace of a set
of points in
is the hypergraph whose blocks are all non-empty
where
.
INPUT:
points
– a set of points.min_size
(integer; default 1) – minimum size of the sets to keep. By default all empty sets are discarded, i.e.min_size=1
.multiset
(boolean; defaultTrue
) – whether to keep multiple copies of the same set.
Note
This method goes over all sets of
self
before building a newIncidenceStructure
(which involves some relabelling and sorting). It probably should not be called in a performance-critical 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
-
sage.combinat.designs.incidence_structures.
IncidenceStructureFromMatrix
(M, name=None)¶ Deprecated function that builds an incidence structure from a matrix.
You should now use
designs.IncidenceStructure(incidence_matrix=M)
.INPUT:
M
– a binary matrix. Creates a set of “points” from the rows and a set of “blocks” from the columns.
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