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:

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.
block_sizes()	Return the set of block sizes.
blocks()	Return the list of blocks.
canonical_label()	Return a canonical label for the incidence structure.
coloring()	Compute a (weak) \(k\)-coloring of the hypergraph
complement()	Return the complement of the incidence structure.
copy()	Return a copy of the incidence structure.
degree()	Return the degree of a point p (or a set of points).
degrees()	Return the degree of all sets of given size, or the degree of all points.
dual()	Return the dual of the incidence structure.
edge_coloring()	Compute a proper edge-coloring.
ground_set()	Return the ground set (i.e the list of points).
incidence_graph()	Return the incidence graph of the incidence structure
incidence_matrix()	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.
induced_substructure()	Return the substructure induced by a set of points.
intersection_graph()	Return the intersection graph of the incidence structure.
is_berge_cyclic()	Check whether self is a Berge-Cyclic uniform hypergraph.
is_connected()	Test whether the design is connected.
is_generalized_quadrangle()	Test if the incidence structure is a generalized quadrangle.
is_isomorphic()	Return whether the two incidence structures are isomorphic.
is_regular()	Test whether the incidence structure is \(r\)-regular.
is_resolvable()	Test whether the hypergraph is resolvable
is_simple()	Test whether this design is simple (i.e. no repeated block).
is_spread()	Check whether the input is a spread for self.
is_t_design()	Test whether self is a \(t-(v,k,l)\) design.
is_uniform()	Test whether the incidence structure is \(k\)-uniform
isomorphic_substructures_iterator()	Iterates over all copies of H2 contained in self.
num_blocks()	Return the number of blocks.
num_points()	Return the size of the ground set.
packing()	Return a maximum packing
rank()	Return the rank of the hypergraph (the maximum size of a block).
relabel()	Relabel the ground set
trace()	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 (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, 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. If points is an integer \(v\), then the set is considered to be \(\{0, ..., v-1\}\).

  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 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: 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 to False, but in that case, your input must be a list of lists and the ground set must be \({0, ..., v-1}\):

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 self-dual 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 non-integer 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,...,n-1\}\) 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 to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – non-negative 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; see MixedIntegerLinearProgram.get_values().

EXAMPLES:

The Fano plane has chromatic number 3:

sage: len(designs.steiner_triple_system(7).coloring())
3

One admissible 3-coloring:

sage: designs.steiner_triple_system(7).coloring() # not tested - architecture-dependent
[[0, 2, 5, 1], [4, 3], [6]]

The chromatic number of a graph is equal to the chromatic number of its 2-uniform 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 in self.

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

• 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 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))

REFERENCE:

• Soicher, Leonard, Design package manual, available at https://www.gap-system.org/Manuals/pkg/design/htm/CHAP003.htm

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: 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 of ground_set(), and appear in the same order. Similarly, the following vertices represent the elements of blocks(), and appear in the same order.

  • labels is True, the points keep their original labels, and the blocks are Set 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() mix Set() and non-Set 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 if i is in block B_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 new IncidenceStructure (which involves some relabelling and sorting). It probably should not be called in a performance-critical 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 set sizes.

INPUT:

• sizes – a list/set of integers. For convenience, setting sizes to 5 has the same effect as sizes=[5]. When set to None (default), behaves as sizes=PositiveIntegers().

EXAMPLES:

The intersection graph of a balanced_incomplete_block_design() is a strongly 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 Berge-Cyclic 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 Berge-cyclic if its incidence graph is cyclic. It is called “Berge-acyclic” 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 methods is_regular() and is_uniform().

INPUT:

• verbose (boolean) – whether to print an explanation when the instance is not a generalized quadrangle.

• parameters (boolean; False) – if set to True, the function returns a pair (s,t) instead of True answers. In this case, \(s\) and \(t\) are the integers defined above if they exist (each can be set to False 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 from self to other 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. If r is set to None (default), the method returns either False or the integer r 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 to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• 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 to True by default.

• integrality_tolerance – parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.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 non-resolvable 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 to None by default. The function tests whether the design is a t-(v,k,l) design using the provided values and guesses the others. Note that \(l`\) cannot be specified if t is not.

• return_parameters (boolean)– whether to return the parameters of the \(t\)-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 = 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. If k is set to None (default), the method returns either False or the integer k 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 in self.

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 an IncidenceStructure object.

• induced (boolean) – whether to require the copies to be induced. Set to False 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 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 Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• 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; see MixedIntegerLinearProgram.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 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,...,n-1\}\) 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: 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 non-empty \(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; default True) – whether to keep multiple copies of the same set.

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 performance-critical 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