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:
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. 

Return the set of block sizes. 

Return the list of blocks. 

Return a canonical label for the incidence structure. 

Compute a (weak) \(k\)coloring of the hypergraph 

Return the complement of the incidence structure. 

Return a copy of the incidence structure. 

Return the degree of a point 

Return the degree of all sets of given size, or the degree of all points. 

Return the dual of the incidence structure. 

Compute a proper edgecoloring. 

Return the ground set (i.e the list of points). 

Return the incidence graph of the incidence structure 

Return the incidence matrix \(A\) of the design. A is a \((v \times b)\) matrix defined by: 

Return the substructure induced by a set of points. 

Return the intersection graph of the incidence structure. 

Check whether 

Test whether the design is connected. 

Test if the incidence structure is a generalized quadrangle. 

Return whether the two incidence structures are isomorphic. 

Test whether the incidence structure is \(r\)regular. 

Test whether the hypergraph is resolvable 

Test whether this design is simple (i.e. no repeated block). 

Check whether the input is a spread for 

Test whether 

Test whether the incidence structure is \(k\)uniform 

Iterates over all copies of 

Return the number of blocks. 

Return the size of the ground set. 

Return a maximum packing 

Return the rank of the hypergraph (the maximum size of a block). 

Relabel the ground set 

Return the trace of a set of points. 
REFERENCES:
 1
Block designs and incidence structures from wikipedia, Wikipedia article Block_design Wikipedia article Incidence_structure
 2
E. Assmus, J. Key, Designs and their codes, CUP, 1992.
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
Methods#
 class sage.combinat.designs.incidence_structures.IncidenceStructure(points=None, blocks=None, incidence_matrix=None, name=None, check=True, 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 \(v\), then the set is considered to be \(\{0, ..., v1\}\).Note
The following syntax, where
points
is omitted, automatically defines the ground set as the union of the blocks:sage: H = IncidenceStructure([['a','b','c'],['c','d','e']]) sage: sorted(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: 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: 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 = 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 = IncidenceStructure([0,1,2], [[0],[0,2]]) sage: B = IncidenceStructure([1,0,2], [[0],[2,0]]) sage: B == A True sage: C = BlockDesign(2, [[0], [1,0]]) sage: D = 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 \({0, ..., v1}\):sage: blocks = [[0,1],[2,0],[1,2]] # a list of lists of integers sage: I = 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 selfdual example:
sage: IS = IncidenceStructure(list(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 = IncidenceStructure('abc', ('ab','ac','bc')) sage: I.automorphism_group() Permutation Group with generators [('b','c'), ('a','b')] sage: IncidenceStructure([[(1,2),(3,4)]]).automorphism_group() Permutation Group with generators [((1,2),(3,4))]
 block_sizes()#
Return the set of block sizes.
EXAMPLES:
sage: BD = IncidenceStructure(8, [[0,1,3],[1,4,5,6],[1,2],[5,6,7]]) sage: BD.block_sizes() [3, 2, 4, 3] sage: BD = 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 = 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 \(\{0,...,n1\}\) such that isomorphic incidence structures are relabelled to equal objects.
EXAMPLES:
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
 coloring(k, solver=None, verbose=None, integrality_tolerance=0)#
Compute a (weak) \(k\)coloring of the hypergraph
A weak coloring of a hypergraph \(\mathcal H\) is an assignment of colors to its vertices such that no set is monochromatic.
INPUT:
k
(integer) – compute a coloring with \(k\) colors if an integer is provided, otherwise returns an optimal coloring (i.e. with the minimum possible number of colors).solver
– (default:None
) Specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– nonnegative integer (default:0
). Set the level of verbosity you want from the linear program solver. Since the problem is \(NP\)complete, its solving may take some time depending on the graph. A value of 0 means that there will be no message printed by the solver.integrality_tolerance
– parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
EXAMPLES:
The Fano plane has chromatic number 3:
sage: len(designs.steiner_triple_system(7).coloring()) 3
One admissible 3coloring:
sage: designs.steiner_triple_system(7).coloring() # not tested  architecturedependent [[0, 2, 5, 1], [4, 3], [6]]
The chromatic number of a graph is equal to the chromatic number of its 2uniform corresponding hypergraph:
sage: g = graphs.PetersenGraph() sage: H = IncidenceStructure(g.edges(sort=True, labels=False)) sage: len(g.coloring()) 3 sage: len(H.coloring()) 3
 complement(uniform=False)#
Return the complement of the incidence structure.
Two different definitions of “complement” are made available, according to the value of
uniform
.INPUT:
uniform
(boolean) –if set to
False
(default), returns the incidence structure whose blocks are the complements of all blocks of the incidence structure.If set to
True
and the incidence structure is \(k\)uniform, returns the incidence structure whose blocks are all \(k\)sets of the ground set that do not appear inself
.
EXAMPLES:
The complement of a
BalancedIncompleteBlockDesign
is also a \(2\)design:sage: bibd = designs.balanced_incomplete_block_design(13,4) sage: bibd.is_t_design(return_parameters=True) (True, (2, 13, 4, 1)) sage: bibd.complement().is_t_design(return_parameters=True) (True, (2, 13, 9, 6))
The “uniform” complement of a graph is a graph:
sage: g = graphs.PetersenGraph() sage: G = IncidenceStructure(g.edges(sort=True, labels=False)) sage: H = G.complement(uniform=True) sage: h = Graph(H.blocks()) sage: g == h False sage: g == h.complement() True
 copy()#
Return a copy of the incidence structure.
EXAMPLES:
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
 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).values()) 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 thegap_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))
REFERENCE:
Soicher, Leonard, Design package manual, available at https://www.gapsystem.org/Manuals/pkg/design/htm/CHAP003.htm
 edge_coloring()#
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
 ground_set()#
Return the ground set (i.e the list of points).
EXAMPLES:
sage: IncidenceStructure(3, [[0,1],[0,2]]).ground_set() [0, 1, 2]
 incidence_graph(labels=False)#
Return the incidence graph of the incidence structure
A point and a block are adjacent in this graph whenever they are incident.
INPUT:
labels
(boolean) – whether to return a graph whose vertices are integers, or labelled elements.labels is False
(default) – in this case the first vertices of the graphs are the elements ofground_set()
, and appear in the same order. Similarly, the following vertices represent the elements ofblocks()
, and appear in the same order.labels is True
, the points keep their original labels, and the blocks areSet
objects.Note that the labelled incidence graph can be incorrect when blocks are repeated, and on some (rare) occasions when the elements of
ground_set()
mixSet()
and nonSet
objects.
EXAMPLES:
sage: BD = 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
 incidence_matrix()#
Return the incidence matrix \(A\) of the design. A is a \((v \times b)\) matrix defined by:
A[i,j] = 1
ifi
is in blockB_j
and 0 otherwise.EXAMPLES:
sage: BD = 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 = 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 \(\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:
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 performancecritical code.EXAMPLES:
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
 intersection_graph(sizes=None)#
Return the intersection graph of the incidence structure.
The vertices of this graph are the
blocks()
of the incidence structure. Two of them are adjacent if the size of their intersection belongs to the setsizes
.INPUT:
sizes
– a list/set of integers. For convenience, settingsizes
to5
has the same effect assizes=[5]
. When set toNone
(default), behaves assizes=PositiveIntegers()
.
EXAMPLES:
The intersection graph of a
balanced_incomplete_block_design()
is astrongly regular graph
(when it is not trivial):sage: BIBD = designs.balanced_incomplete_block_design(19,3) sage: G = BIBD.intersection_graph(1) sage: G.is_strongly_regular(parameters=True) (57, 24, 11, 9)
 is_berge_cyclic()#
Check whether
self
is a BergeCyclic uniform hypergraph.A \(k\)uniform Berge cycle (named after Claude Berge) of length \(\ell\) is a cyclic list of distinct \(k\)sets \(F_1,\ldots,F_\ell\), \(\ell>1\), and distinct vertices \(C = \{v_1,\ldots,v_\ell\}\) such that for each \(1\le i\le \ell\), \(F_i\) contains \(v_i\) and \(v_{i+1}\) (where \(v_{l+1} = v_1\)).
A uniform hypergraph is Bergecyclic if its incidence graph is cyclic. It is called “Bergeacyclic” otherwise.
For more information, see [Fag1983] and Wikipedia article Hypergraph.
EXAMPLES:
sage: Hypergraph(5, [[1, 2, 3], [2, 3 ,4]]).is_berge_cyclic() True sage: Hypergraph(6, [[1, 2, 3], [3 ,4, 5]]).is_berge_cyclic() False
 is_connected()#
Test whether the design is connected.
EXAMPLES:
sage: IncidenceStructure(3, [[0,1],[0,2]]).is_connected() True sage: IncidenceStructure(4, [[0,1],[2,3]]).is_connected() False
 is_generalized_quadrangle(verbose=False, parameters=False)#
Test if the incidence structure is a generalized quadrangle.
An incidence structure is a generalized quadrangle iff (see [BH2012], section 9.6):
two blocks intersect on at most one point.
For every point \(p\) not in a block \(B\), there is a unique block \(B'\) intersecting both \(\{p\}\) and \(B\)
It is a regular generalized quadrangle if furthermore:
it is \(s+1\)
uniform
for some positive integer \(s\).it is \(t+1\)
regular
for some positive integer \(t\).
For more information, see the Wikipedia article Generalized_quadrangle.
Note
Some references (e.g. [PT2009] or Wikipedia article Generalized_quadrangle) only allow regular generalized quadrangles. To use such a definition, see the
parameters
optional argument described below, or the methodsis_regular()
andis_uniform()
.INPUT:
verbose
(boolean) – whether to print an explanation when the instance is not a generalized quadrangle.parameters
(boolean;False
) – if set toTrue
, the function returns a pair(s,t)
instead ofTrue
answers. In this case, \(s\) and \(t\) are the integers defined above if they exist (each can be set toFalse
otherwise).
EXAMPLES:
sage: h = designs.CremonaRichmondConfiguration() sage: h.is_generalized_quadrangle() True
This is actually a regular generalized quadrangle:
sage: h.is_generalized_quadrangle(parameters=True) (2, 2)
 is_isomorphic(other, certificate=False)#
Return whether the two incidence structures are isomorphic.
INPUT:
other
– an incidence structure.certificate
(boolean) – whether to return an isomorphism fromself
toother
instead of a boolean answer.
EXAMPLES:
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}
 is_regular(r=None)#
Test whether the incidence structure is \(r\)regular.
An incidence structure is said to be \(r\)regular if all its points are incident with exactly \(r\) blocks.
INPUT:
r
(integer)
OUTPUT:
If
r
is defined, a boolean is returned. Ifr
is set toNone
(default), the method returns eitherFalse
or the integerr
such that the incidence structure is \(r\)regular.Warning
In case of \(0\)regular incidence structure, beware that
if not H.is_regular()
is a satisfied condition.EXAMPLES:
sage: designs.balanced_incomplete_block_design(7,3).is_regular() 3 sage: designs.balanced_incomplete_block_design(7,3).is_regular(r=3) True sage: designs.balanced_incomplete_block_design(7,3).is_regular(r=4) False
 is_resolvable(certificate, solver=False, verbose=None, check=0, integrality_tolerance=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 MILP solver (CPLEX, Gurobi, …).
INPUT:
certificate
(boolean) – whether to return the classes along with the binary answer (see examples below).solver
– (default:None
) Specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP 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.integrality_tolerance
– parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
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, [])
 is_simple()#
Test whether this design is simple (i.e. no repeated block).
EXAMPLES:
sage: IncidenceStructure(3, [[0,1],[1,2],[0,2]]).is_simple() True sage: 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 = IncidenceStructure(V, B) sage: I.is_simple() True sage: I2 = IncidenceStructure(V, B*2) sage: I2.is_simple() False
 is_spread(spread)#
Check whether the input is a spread for
self
.A spread of an incidence structure \((P, B)\) is a subset of \(B\) which forms a partition of \(P\).
INPUT:
spread
– iterable; defines the spread
EXAMPLES:
sage: E = IncidenceStructure([[1, 2, 3], [4, 5, 6], [1, 5, 6]]) sage: E.is_spread([[1, 2, 3], [4, 5, 6]]) True sage: E.is_spread([1, 2, 3, 4, 5, 6]) Traceback (most recent call last): ... TypeError: 'sage.rings.integer.Integer' object is not iterable sage: E.is_spread([[1, 2, 3, 4], [5, 6]]) False
Order of blocks or of points within each block doesn’t matter:
sage: E = IncidenceStructure([[1, 2, 3], [4, 5, 6], [1, 5, 6]]) sage: E.is_spread([[5, 6, 4], [3, 1, 2]]) True
 is_t_design(t=None, v=None, k=None, l=None, return_parameters=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:
the underlying set has cardinality \(v\)
the blocks have size \(k\)
each \(t\)subset of points is covered by \(\lambda\) 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 that \(l\) cannot be specified ift
is not.return_parameters
(boolean)– whether to return the parameters of the \(t\)design. If set toTrue
, 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 = 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 = IncidenceStructure(8, blocks) sage: S4_8.is_t_design(3,8,4,1) True sage: blocks = designs.steiner_quadruple_system(14) sage: S4_14 = 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 = IncidenceStructure(4,[[],[]]) sage: D.is_t_design(return_parameters=True) (True, (0, 4, 0, 2)) sage: D = IncidenceStructure(4, [[0,1],[0,2],[0,3]]) sage: D.is_t_design(return_parameters=True) (True, (0, 4, 2, 3)) sage: D = IncidenceStructure(4, [[0],[1],[2],[3]]) sage: D.is_t_design(return_parameters=True) (True, (1, 4, 1, 1)) sage: D = IncidenceStructure(4,[[0,1],[2,3]]) sage: D.is_t_design(return_parameters=True) (True, (1, 4, 2, 1)) sage: D = IncidenceStructure(4, [list(range(4))]) sage: D.is_t_design(return_parameters=True) (True, (4, 4, 4, 1))
 is_uniform(k=None)#
Test whether the incidence structure is \(k\)uniform
An incidence structure is said to be \(k\)uniform if all its blocks have size \(k\).
INPUT:
k
(integer)
OUTPUT:
If
k
is defined, a boolean is returned. Ifk
is set toNone
(default), the method returns eitherFalse
or the integerk
such that the incidence structure is \(k\)uniform.Warning
In case of \(0\)uniform incidence structure, beware that
if not H.is_uniform()
is a satisfied condition.EXAMPLES:
sage: designs.balanced_incomplete_block_design(7,3).is_uniform() 3 sage: designs.balanced_incomplete_block_design(7,3).is_uniform(k=3) True sage: designs.balanced_incomplete_block_design(7,3).is_uniform(k=4) False
 isomorphic_substructures_iterator(H2, induced=False)#
Iterates over all copies of
H2
contained inself
.A hypergraph \(H_1\) contains an isomorphic copy of a hypergraph \(H_2\) if there exists an injection \(f:V(H_2)\mapsto V(H_1)\) such that for any set \(S_2\in E(H_2)\) the set \(S_1=f(S2)\) belongs to \(E(H_1)\).
It is an induced copy if no other set of \(E(H_1)\) is contained in \(f(V(H_2))\), i.e. \(E(H_2)=\{S:S\in E(H_1)\text{ and }f(V(H_2))\}\).
This function lists all such injections. In particular, the number of copies of \(H\) 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 \(C_5\) in Petersen’s graph ?
sage: P = graphs.PetersenGraph() sage: C = graphs.CycleGraph(5) sage: IP = IncidenceStructure(P.edges(sort=True, labels=False)) sage: IC = IncidenceStructure(C.edges(sort=True, labels=False)) sage: sum(1 for _ in IP.isomorphic_substructures_iterator(IC)) 120
As the automorphism group of \(C_5\) has size 10, the number of distinct unlabelled copies is 12. Let us check that all functions returned correspond to an actual \(C_5\) 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(sort=True, 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], loops=False) sage: IP = IncidenceStructure(P.edges(sort=True, labels=False)) sage: IC = IncidenceStructure(C.edges(sort=True, 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 \(H\) 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 = 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 = IncidenceStructure(4, [[0,1],[0,2],[0,3],[1,2], [1,2,3]]) sage: B.num_points() 4
 packing(solver, verbose=None, integrality_tolerance=0)#
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:
solver
– (default:None
) Specify a Mixed Integer Linear Programming (MILP) 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.integrality_tolerance
– parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
EXAMPLES:
sage: P = IncidenceStructure([[1,2],[3,4],[2,3]]).packing() sage: sorted(sorted(b) for b in P) [[1, 2], [3, 4]] sage: len(designs.steiner_triple_system(9).packing()) 3
 rank()#
Return the rank of the hypergraph (the maximum size of a block).
EXAMPLES:
sage: h = Hypergraph(8, [[0,1,3],[1,4,5,6],[1,2]]) sage: h.rank() 4
 relabel(perm=None, inplace=True)#
Relabel the ground set
INPUT:
perm
– can be one ofa 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 on \(\{0,1,...,n1\}\) in the ordering given byground_set()
.
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: 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: 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: TD.blocks()[:3] [[0, 5, 10, 15, 20], [0, 6, 12, 18, 24], [0, 7, 14, 16, 23]]
 trace(points, min_size=1, multiset=True)#
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:
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 performancecritical code.EXAMPLES:
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