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()	Iterate 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

  sage: H = IncidenceStructure([['a','b','c'],['c','d','e']])
  sage: sorted(H.ground_set())
  ['a', 'b', 'c', 'd', 'e']
  

  Python

  >>> from sage.all import *
  >>> H = IncidenceStructure([['a','b','c'],['c','d','e']])
  >>> 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 – 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

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

Python

>>> from sage.all import *
>>> IncidenceStructure(Integer(7), [[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(3),Integer(4)],[Integer(0),Integer(5),Integer(6)],[Integer(1),Integer(3),Integer(5)],[Integer(1),Integer(4),Integer(6)],[Integer(2),Integer(3),Integer(6)],[Integer(2),Integer(4),Integer(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

sage: IncidenceStructure([[1,2,3],[2,3,4]])
Incidence structure with 4 points and 2 blocks

Python

>>> from sage.all import *
>>> IncidenceStructure([[Integer(1),Integer(2),Integer(3)],[Integer(2),Integer(3),Integer(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

sage: m = matrix([[0,1,0],[0,0,1],[1,0,1],[1,1,1]])                             # needs sage.modules
sage: IncidenceStructure(m)                                                     # needs sage.modules
Incidence structure with 4 points and 3 blocks

Python

>>> from sage.all import *
>>> m = matrix([[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)],[Integer(1),Integer(0),Integer(1)],[Integer(1),Integer(1),Integer(1)]])                             # needs sage.modules
>>> IncidenceStructure(m)                                                     # needs sage.modules
Incidence structure with 4 points and 3 blocks

The points can be any (hashable) object:

Sage

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')]]

Python

>>> from sage.all import *
>>> V = [(Integer(0),'a'),(Integer(0),'b'),(Integer(1),'a'),(Integer(1),'b')]
>>> B = [(V[Integer(0)],V[Integer(1)],V[Integer(2)]), (V[Integer(1)],V[Integer(2)]), (V[Integer(0)],V[Integer(2)])]
>>> I = IncidenceStructure(V, B)
>>> I.ground_set()
[(0, 'a'), (0, 'b'), (1, 'a'), (1, 'b')]
>>> 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 Issue #11333):

Sage

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

Python

>>> from sage.all import *
>>> A = IncidenceStructure([Integer(0),Integer(1),Integer(2)], [[Integer(0)],[Integer(0),Integer(2)]])
>>> B = IncidenceStructure([Integer(1),Integer(0),Integer(2)], [[Integer(0)],[Integer(2),Integer(0)]])
>>> B == A
True

>>> C = BlockDesign(Integer(2), [[Integer(0)], [Integer(1),Integer(0)]])
>>> D = BlockDesign(Integer(2), [[Integer(0),Integer(1)], [Integer(0)]])
>>> 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

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

Python

>>> from sage.all import *
>>> blocks = [[Integer(0),Integer(1)],[Integer(2),Integer(0)],[Integer(1),Integer(2)]]  # a list of lists of integers
>>> I = IncidenceStructure(Integer(3), blocks, copy=False)
>>> 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

sage: # needs sage.groups sage.rings.finite_rings
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

Python

>>> from sage.all import *
>>> # needs sage.groups sage.rings.finite_rings
>>> P = designs.DesarguesianProjectivePlaneDesign(Integer(2)); P
(7,3,1)-Balanced Incomplete Block Design
>>> G = P.automorphism_group()
>>> G.is_isomorphic(PGL(Integer(3),Integer(2)))
True
>>> G
Permutation Group with generators [...]
>>> G.cardinality()
168

A non self-dual example:

Sage

sage: IS = IncidenceStructure(list(range(4)), [[0,1,2,3],[1,2,3]])
sage: IS.automorphism_group().cardinality()                                 # needs sage.groups
6
sage: IS.dual().automorphism_group().cardinality()                          # needs sage.groups sage.modules
1

Python

>>> from sage.all import *
>>> IS = IncidenceStructure(list(range(Integer(4))), [[Integer(0),Integer(1),Integer(2),Integer(3)],[Integer(1),Integer(2),Integer(3)]])
>>> IS.automorphism_group().cardinality()                                 # needs sage.groups
6
>>> IS.dual().automorphism_group().cardinality()                          # needs sage.groups sage.modules
1

Examples with non-integer points:

Sage

sage: I = IncidenceStructure('abc', ('ab','ac','bc'))
sage: I.automorphism_group()                                                # needs sage.groups
Permutation Group with generators [('b','c'), ('a','b')]
sage: IncidenceStructure([[(1,2),(3,4)]]).automorphism_group()              # needs sage.groups
Permutation Group with generators [((1,2),(3,4))]

Python

>>> from sage.all import *
>>> I = IncidenceStructure('abc', ('ab','ac','bc'))
>>> I.automorphism_group()                                                # needs sage.groups
Permutation Group with generators [('b','c'), ('a','b')]
>>> IncidenceStructure([[(Integer(1),Integer(2)),(Integer(3),Integer(4))]]).automorphism_group()              # needs sage.groups
Permutation Group with generators [((1,2),(3,4))]

block_sizes()

Return the set of block sizes.

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> BD = IncidenceStructure(Integer(8), [[Integer(0),Integer(1),Integer(3)],[Integer(1),Integer(4),Integer(5),Integer(6)],[Integer(1),Integer(2)],[Integer(5),Integer(6),Integer(7)]])
>>> BD.block_sizes()
[3, 2, 4, 3]
>>> BD = IncidenceStructure(Integer(7),[[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(3),Integer(4)],[Integer(0),Integer(5),Integer(6)],[Integer(1),Integer(3),Integer(5)],[Integer(1),Integer(4),Integer(6)],[Integer(2),Integer(3),Integer(6)],[Integer(2),Integer(4),Integer(5)]])
>>> BD.block_sizes()
[3, 3, 3, 3, 3, 3, 3]

blocks()

Return the list of blocks.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> BD = IncidenceStructure(Integer(7),[[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(3),Integer(4)],[Integer(0),Integer(5),Integer(6)],[Integer(1),Integer(3),Integer(5)],[Integer(1),Integer(4),Integer(6)],[Integer(2),Integer(3),Integer(6)],[Integer(2),Integer(4),Integer(5)]])
>>> 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

sage: # needs sage.schemes
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

Python

>>> from sage.all import *
>>> # needs sage.schemes
>>> fano1 = designs.balanced_incomplete_block_design(Integer(7),Integer(3))
>>> fano2 = designs.projective_plane(Integer(2))
>>> fano1 == fano2
False
>>> fano1.relabel(fano1.canonical_label())
>>> fano2.relabel(fano2.canonical_label())
>>> 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 – 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; see MixedIntegerLinearProgram.get_values()

EXAMPLES:

The Fano plane has chromatic number 3:

Sage

sage: len(designs.steiner_triple_system(7).coloring())                      # needs sage.numerical.mip
3

Python

>>> from sage.all import *
>>> len(designs.steiner_triple_system(Integer(7)).coloring())                      # needs sage.numerical.mip
3

One admissible 3-coloring:

Sage

sage: designs.steiner_triple_system(7).coloring()   # not tested            # needs sage.numerical.mip
[[0, 2, 5, 1], [4, 3], [6]]

Python

>>> from sage.all import *
>>> designs.steiner_triple_system(Integer(7)).coloring()   # not tested            # needs sage.numerical.mip
[[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

sage: g = graphs.PetersenGraph()
sage: H = IncidenceStructure(g.edges(sort=True, labels=False))
sage: len(g.coloring())
3
sage: len(H.coloring())                                                     # needs sage.numerical.mip
3

Python

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> H = IncidenceStructure(g.edges(sort=True, labels=False))
>>> len(g.coloring())
3
>>> len(H.coloring())                                                     # needs sage.numerical.mip
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

sage: bibd = designs.balanced_incomplete_block_design(13,4)                 # needs sage.schemes
sage: bibd.is_t_design(return_parameters=True)                              # needs sage.schemes
(True, (2, 13, 4, 1))
sage: bibd.complement().is_t_design(return_parameters=True)                 # needs sage.schemes
(True, (2, 13, 9, 6))

Python

>>> from sage.all import *
>>> bibd = designs.balanced_incomplete_block_design(Integer(13),Integer(4))                 # needs sage.schemes
>>> bibd.is_t_design(return_parameters=True)                              # needs sage.schemes
(True, (2, 13, 4, 1))
>>> bibd.complement().is_t_design(return_parameters=True)                 # needs sage.schemes
(True, (2, 13, 9, 6))

The “uniform” complement of a graph is a graph:

Sage

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

Python

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> G = IncidenceStructure(g.edges(sort=True, labels=False))
>>> H = G.complement(uniform=True)
>>> h = Graph(H.blocks())
>>> g == h
False
>>> g == h.complement()
True

copy()

Return a copy of the incidence structure.

EXAMPLES:

Sage

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'

Python

>>> from sage.all import *
>>> IS = IncidenceStructure([[Integer(1),Integer(2),Integer(3),"e"]], name='Test')
>>> IS
Incidence structure with 4 points and 1 blocks
>>> copy(IS)
Incidence structure with 4 points and 1 blocks
>>> [Integer(1), Integer(2), Integer(3), 'e'] in copy(IS)
True
>>> 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 (default: False); whether to interpret the argument as a set of point or as a point (default)

EXAMPLES:

Sage

sage: designs.steiner_triple_system(9).degree(3)
4
sage: designs.steiner_triple_system(9).degree({1,2},subset=True)
1

Python

>>> from sage.all import *
>>> designs.steiner_triple_system(Integer(9)).degree(Integer(3))
4
>>> designs.steiner_triple_system(Integer(9)).degree({Integer(1),Integer(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

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}

Python

>>> from sage.all import *
>>> IncidenceStructure([[Integer(1),Integer(2),Integer(3)],[Integer(1),Integer(4)]]).degrees(Integer(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

sage: S13 = designs.steiner_triple_system(13)
sage: all(v == 1 for v in S13.degrees(2).values())
True

Python

>>> from sage.all import *
>>> S13 = designs.steiner_triple_system(Integer(13))
>>> all(v == Integer(1) for v in S13.degrees(Integer(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

sage: PP = designs.DesarguesianProjectivePlaneDesign(4)                     # needs sage.rings.finite_rings
sage: PP.dual().is_t_design(return_parameters=True)                         # needs sage.modules sage.rings.finite_rings
(True, (2, 21, 5, 1))

Python

>>> from sage.all import *
>>> PP = designs.DesarguesianProjectivePlaneDesign(Integer(4))                     # needs sage.rings.finite_rings
>>> PP.dual().is_t_design(return_parameters=True)                         # needs sage.modules sage.rings.finite_rings
(True, (2, 21, 5, 1))

REFERENCE:

• Leonard Soicher, Design package manual

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

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

Python

>>> from sage.all import *
>>> H = Hypergraph([{Integer(1),Integer(2),Integer(3)},{Integer(2),Integer(3),Integer(4)},{Integer(3),Integer(4),Integer(5)},{Integer(4),Integer(5),Integer(6)}]); H
Incidence structure with 6 points and 4 blocks
>>> C = H.edge_coloring()
>>> C # random
[[[3, 4, 5]], [[2, 3, 4]], [[4, 5, 6], [1, 2, 3]]]
>>> 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

sage: IncidenceStructure(3, [[0,1],[0,2]]).ground_set()
[0, 1, 2]

Python

>>> from sage.all import *
>>> IncidenceStructure(Integer(3), [[Integer(0),Integer(1)],[Integer(0),Integer(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

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()                                                  # needs sage.modules
Bipartite graph on 14 vertices
sage: A = BD.incidence_matrix()                                             # needs sage.modules
sage: Graph(block_matrix([[A*0, A],                                         # needs sage.modules
....:                     [A.transpose(),A*0]])) == BD.incidence_graph()
True

Python

>>> from sage.all import *
>>> BD = IncidenceStructure(Integer(7), [[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(3),Integer(4)],[Integer(0),Integer(5),Integer(6)],[Integer(1),Integer(3),Integer(5)],
...                             [Integer(1),Integer(4),Integer(6)],[Integer(2),Integer(3),Integer(6)],[Integer(2),Integer(4),Integer(5)]])
>>> BD.incidence_graph()                                                  # needs sage.modules
Bipartite graph on 14 vertices
>>> A = BD.incidence_matrix()                                             # needs sage.modules
>>> Graph(block_matrix([[A*Integer(0), A],                                         # needs sage.modules
...                     [A.transpose(),A*Integer(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

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()                                                 # needs sage.modules
[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()                                                  # needs sage.modules
[1 1 1 0]
[1 1 0 0]
[0 1 1 1]

Python

>>> from sage.all import *
>>> BD = IncidenceStructure(Integer(7), [[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(3),Integer(4)],[Integer(0),Integer(5),Integer(6)],[Integer(1),Integer(3),Integer(5)],
...                             [Integer(1),Integer(4),Integer(6)],[Integer(2),Integer(3),Integer(6)],[Integer(2),Integer(4),Integer(5)]])
>>> BD.block_sizes()
[3, 3, 3, 3, 3, 3, 3]
>>> BD.incidence_matrix()                                                 # needs sage.modules
[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]

>>> I = IncidenceStructure('abc', ('ab','abc','ac','c'))
>>> I.incidence_matrix()                                                  # needs sage.modules
[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 – 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

sage: F = designs.steiner_triple_system(7)
sage: F.induced_substructure([0..5])
Incidence structure with 6 points and 4 blocks

Python

>>> from sage.all import *
>>> F = designs.steiner_triple_system(Integer(7))
>>> F.induced_substructure((ellipsis_range(Integer(0),Ellipsis,Integer(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 – 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

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)

Python

>>> from sage.all import *
>>> BIBD =  designs.balanced_incomplete_block_design(Integer(19),Integer(3))
>>> G = BIBD.intersection_graph(Integer(1))
>>> 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

sage: Hypergraph(5, [[1, 2, 3], [2, 3, 4]]).is_berge_cyclic()               # needs sage.modules
True
sage: Hypergraph(6, [[1, 2, 3], [3, 4, 5]]).is_berge_cyclic()               # needs sage.modules
False

Python

>>> from sage.all import *
>>> Hypergraph(Integer(5), [[Integer(1), Integer(2), Integer(3)], [Integer(2), Integer(3), Integer(4)]]).is_berge_cyclic()               # needs sage.modules
True
>>> Hypergraph(Integer(6), [[Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)]]).is_berge_cyclic()               # needs sage.modules
False

is_connected()

Test whether the design is connected.

EXAMPLES:

Sage

sage: IncidenceStructure(3, [[0,1],[0,2]]).is_connected()
True
sage: IncidenceStructure(4, [[0,1],[2,3]]).is_connected()
False

Python

>>> from sage.all import *
>>> IncidenceStructure(Integer(3), [[Integer(0),Integer(1)],[Integer(0),Integer(2)]]).is_connected()
True
>>> IncidenceStructure(Integer(4), [[Integer(0),Integer(1)],[Integer(2),Integer(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

sage: h = designs.CremonaRichmondConfiguration()                            # needs networkx
sage: h.is_generalized_quadrangle()                                         # needs networkx
True

Python

>>> from sage.all import *
>>> h = designs.CremonaRichmondConfiguration()                            # needs networkx
>>> h.is_generalized_quadrangle()                                         # needs networkx
True

This is actually a regular generalized quadrangle:

Sage

sage: h.is_generalized_quadrangle(parameters=True)                          # needs networkx
(2, 2)

Python

>>> from sage.all import *
>>> h.is_generalized_quadrangle(parameters=True)                          # needs networkx
(2, 2)

is_isomorphic(other, certificate=False)

Return whether the two incidence structures are isomorphic.

INPUT:

• other – an incidence structure

• certificate – boolean (default: False); whether to return an isomorphism from self to other instead of a boolean answer

EXAMPLES:

Sage

sage: # needs sage.schemes
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}

Python

>>> from sage.all import *
>>> # needs sage.schemes
>>> fano1 = designs.balanced_incomplete_block_design(Integer(7),Integer(3))
>>> fano2 = designs.projective_plane(Integer(2))
>>> fano1.is_isomorphic(fano2)
True
>>> 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

sage: designs.balanced_incomplete_block_design(7,3).is_regular()            # needs sage.schemes
3
sage: designs.balanced_incomplete_block_design(7,3).is_regular(r=3)         # needs sage.schemes
True
sage: designs.balanced_incomplete_block_design(7,3).is_regular(r=4)         # needs sage.schemes
False

Python

>>> from sage.all import *
>>> designs.balanced_incomplete_block_design(Integer(7),Integer(3)).is_regular()            # needs sage.schemes
3
>>> designs.balanced_incomplete_block_design(Integer(7),Integer(3)).is_regular(r=Integer(3))         # needs sage.schemes
True
>>> designs.balanced_incomplete_block_design(Integer(7),Integer(3)).is_regular(r=Integer(4))         # needs sage.schemes
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 (default: True); whether to check that output is correct before returning it. As this is expected to be useless, you may want to disable it whenever you want speed.

• integrality_tolerance – parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values()

EXAMPLES:

Some resolvable designs:

Sage

sage: TD = designs.transversal_design(2,2,resolvable=True)
sage: TD.is_resolvable()
True

sage: AG = designs.AffineGeometryDesign(3,1,GF(2))                          # needs sage.combinat
sage: AG.is_resolvable()                                                    # needs sage.combinat
True

Python

>>> from sage.all import *
>>> TD = designs.transversal_design(Integer(2),Integer(2),resolvable=True)
>>> TD.is_resolvable()
True

>>> AG = designs.AffineGeometryDesign(Integer(3),Integer(1),GF(Integer(2)))                          # needs sage.combinat
>>> AG.is_resolvable()                                                    # needs sage.combinat
True

Their classes:

Sage

sage: b, cls = TD.is_resolvable(True)
sage: b
True
sage: cls # random
[[[0, 3], [1, 2]], [[1, 3], [0, 2]]]

sage: # needs sage.combinat
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]]]

Python

>>> from sage.all import *
>>> b, cls = TD.is_resolvable(True)
>>> b
True
>>> cls # random
[[[0, 3], [1, 2]], [[1, 3], [0, 2]]]

>>> # needs sage.combinat
>>> b, cls = AG.is_resolvable(True)
>>> b
True
>>> 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

sage: Fano = designs.balanced_incomplete_block_design(7,3)                  # needs sage.schemes
sage: Fano.is_resolvable()                                                  # needs sage.schemes
False
sage: Fano.is_resolvable(True)                                              # needs sage.schemes
(False, [])

Python

>>> from sage.all import *
>>> Fano = designs.balanced_incomplete_block_design(Integer(7),Integer(3))                  # needs sage.schemes
>>> Fano.is_resolvable()                                                  # needs sage.schemes
False
>>> Fano.is_resolvable(True)                                              # needs sage.schemes
(False, [])

is_simple()

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> IncidenceStructure(Integer(3), [[Integer(0),Integer(1)],[Integer(1),Integer(2)],[Integer(0),Integer(2)]]).is_simple()
True
>>> IncidenceStructure(Integer(3), [[Integer(0)],[Integer(0)]]).is_simple()
False

>>> V = [(Integer(0),'a'),(Integer(0),'b'),(Integer(1),'a'),(Integer(1),'b')]
>>> B = [[V[Integer(0)],V[Integer(1)]], [V[Integer(1)],V[Integer(2)]]]
>>> I = IncidenceStructure(V, B)
>>> I.is_simple()
True
>>> I2 = IncidenceStructure(V, B*Integer(2))
>>> 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

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

Python

>>> from sage.all import *
>>> E = IncidenceStructure([[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(5), Integer(6)], [Integer(1), Integer(5), Integer(6)]])
>>> E.is_spread([[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(5), Integer(6)]])
True
>>> E.is_spread([Integer(1), Integer(2), Integer(3), Integer(4), Integer(5), Integer(6)])
Traceback (most recent call last):
...
TypeError: 'sage.rings.integer.Integer' object is not iterable
>>> E.is_spread([[Integer(1), Integer(2), Integer(3), Integer(4)], [Integer(5), Integer(6)]])
False

Order of blocks or of points within each block doesn’t matter:

Sage

sage: E = IncidenceStructure([[1, 2, 3], [4, 5, 6], [1, 5, 6]])
sage: E.is_spread([[5, 6, 4], [3, 1, 2]])
True

Python

>>> from sage.all import *
>>> E = IncidenceStructure([[Integer(1), Integer(2), Integer(3)], [Integer(4), Integer(5), Integer(6)], [Integer(1), Integer(5), Integer(6)]])
>>> E.is_spread([[Integer(5), Integer(6), Integer(4)], [Integer(3), Integer(1), Integer(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

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))                        # needs sage.combinat
sage: BD.is_t_design(1)                                                     # needs sage.combinat
True
sage: BD.is_t_design(2)                                                     # needs sage.combinat
True

Python

>>> from sage.all import *
>>> fano_blocks = [[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(3),Integer(4)],[Integer(0),Integer(5),Integer(6)],[Integer(1),Integer(3),Integer(5)],[Integer(1),Integer(4),Integer(6)],[Integer(2),Integer(3),Integer(6)],[Integer(2),Integer(4),Integer(5)]]
>>> BD = IncidenceStructure(Integer(7), fano_blocks)
>>> BD.is_t_design()
True
>>> BD.is_t_design(return_parameters=True)
(True, (2, 7, 3, 1))
>>> BD.is_t_design(Integer(2), Integer(7), Integer(3), Integer(1))
True
>>> BD.is_t_design(Integer(1), Integer(7), Integer(3), Integer(3))
True
>>> BD.is_t_design(Integer(0), Integer(7), Integer(3), Integer(7))
True

>>> BD.is_t_design(Integer(0),Integer(6),Integer(3),Integer(7)) or BD.is_t_design(Integer(0),Integer(7),Integer(4),Integer(7)) or BD.is_t_design(Integer(0),Integer(7),Integer(3),Integer(8))
False

>>> BD = designs.AffineGeometryDesign(Integer(3), Integer(1), GF(Integer(2)))                        # needs sage.combinat
>>> BD.is_t_design(Integer(1))                                                     # needs sage.combinat
True
>>> BD.is_t_design(Integer(2))                                                     # needs sage.combinat
True

Steiner triple and quadruple systems are other names for \(2-(v,3,1)\) and \(3-(v,4,1)\) designs:

Sage

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

Python

>>> from sage.all import *
>>> S3_9 = designs.steiner_triple_system(Integer(9))
>>> S3_9.is_t_design(Integer(2),Integer(9),Integer(3),Integer(1))
True

>>> blocks = designs.steiner_quadruple_system(Integer(8))
>>> S4_8 = IncidenceStructure(Integer(8), blocks)
>>> S4_8.is_t_design(Integer(3),Integer(8),Integer(4),Integer(1))
True

>>> blocks = designs.steiner_quadruple_system(Integer(14))
>>> S4_14 = IncidenceStructure(Integer(14), blocks)
>>> S4_14.is_t_design(Integer(3),Integer(14),Integer(4),Integer(1))
True

Some examples of Witt designs that need the gap database:

Sage

sage: # optional - gap_package_design
sage: BD = designs.WittDesign(9)
sage: BD.is_t_design(2,9,3,1)
True
sage: W12 = designs.WittDesign(12)
sage: W12.is_t_design(5,12,6,1)
True
sage: W12.is_t_design(4)
True

Python

>>> from sage.all import *
>>> # optional - gap_package_design
>>> BD = designs.WittDesign(Integer(9))
>>> BD.is_t_design(Integer(2),Integer(9),Integer(3),Integer(1))
True
>>> W12 = designs.WittDesign(Integer(12))
>>> W12.is_t_design(Integer(5),Integer(12),Integer(6),Integer(1))
True
>>> W12.is_t_design(Integer(4))
True

Further examples:

Sage

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

Python

>>> from sage.all import *
>>> D = IncidenceStructure(Integer(4),[[],[]])
>>> D.is_t_design(return_parameters=True)
(True,  (0, 4, 0, 2))

>>> D = IncidenceStructure(Integer(4), [[Integer(0),Integer(1)],[Integer(0),Integer(2)],[Integer(0),Integer(3)]])
>>> D.is_t_design(return_parameters=True)
(True, (0, 4, 2, 3))

>>> D = IncidenceStructure(Integer(4), [[Integer(0)],[Integer(1)],[Integer(2)],[Integer(3)]])
>>> D.is_t_design(return_parameters=True)
(True, (1, 4, 1, 1))

>>> D = IncidenceStructure(Integer(4),[[Integer(0),Integer(1)],[Integer(2),Integer(3)]])
>>> D.is_t_design(return_parameters=True)
(True, (1, 4, 2, 1))

>>> D = IncidenceStructure(Integer(4), [list(range(Integer(4)))])
>>> 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

sage: designs.balanced_incomplete_block_design(7,3).is_uniform()            # needs sage.schemes
3
sage: designs.balanced_incomplete_block_design(7,3).is_uniform(k=3)         # needs sage.schemes
True
sage: designs.balanced_incomplete_block_design(7,3).is_uniform(k=4)         # needs sage.schemes
False

Python

>>> from sage.all import *
>>> designs.balanced_incomplete_block_design(Integer(7),Integer(3)).is_uniform()            # needs sage.schemes
3
>>> designs.balanced_incomplete_block_design(Integer(7),Integer(3)).is_uniform(k=Integer(3))         # needs sage.schemes
True
>>> designs.balanced_incomplete_block_design(Integer(7),Integer(3)).is_uniform(k=Integer(4))         # needs sage.schemes
False

isomorphic_substructures_iterator(H2, induced=False)

Iterate 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 (default: False); whether to require the copies to be induced

EXAMPLES:

How many distinct \(C_5\) in Petersen’s graph ?

Sage

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

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> C = graphs.CycleGraph(Integer(5))
>>> IP = IncidenceStructure(P.edges(sort=True, labels=False))
>>> IC = IncidenceStructure(C.edges(sort=True, labels=False))
>>> sum(Integer(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

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

Python

>>> from sage.all import *
>>> 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

sage: sum(1 for _ in IP.isomorphic_substructures_iterator(IC,induced=True))
120

Python

>>> from sage.all import *
>>> sum(Integer(1) for _ in IP.isomorphic_substructures_iterator(IC,induced=True))
120

They begin to differ if we make one vertex universal:

Sage

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

Python

>>> from sage.all import *
>>> P.add_edges([(Integer(0),x) for x in P], loops=False)
>>> IP = IncidenceStructure(P.edges(sort=True, labels=False))
>>> IC = IncidenceStructure(C.edges(sort=True, labels=False))
>>> sum(Integer(1) for _ in IP.isomorphic_substructures_iterator(IC))
420
>>> sum(Integer(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

sage: H = designs.projective_plane(3)                                       # needs sage.schemes
sage: sum(1 for _ in H.isomorphic_substructures_iterator(H))                # needs sage.schemes
5616
sage: H.automorphism_group().cardinality()                                  # needs sage.groups sage.schemes
5616

Python

>>> from sage.all import *
>>> H = designs.projective_plane(Integer(3))                                       # needs sage.schemes
>>> sum(Integer(1) for _ in H.isomorphic_substructures_iterator(H))                # needs sage.schemes
5616
>>> H.automorphism_group().cardinality()                                  # needs sage.groups sage.schemes
5616

num_blocks()

Return the number of blocks.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> designs.DesarguesianProjectivePlaneDesign(Integer(2)).num_blocks()
7
>>> B = IncidenceStructure(Integer(4), [[Integer(0),Integer(1)],[Integer(0),Integer(2)],[Integer(0),Integer(3)],[Integer(1),Integer(2)], [Integer(1),Integer(2),Integer(3)]])
>>> B.num_blocks()
5

num_points()

Return the size of the ground set.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> designs.DesarguesianProjectivePlaneDesign(Integer(2)).num_points()
7
>>> B = IncidenceStructure(Integer(4), [[Integer(0),Integer(1)],[Integer(0),Integer(2)],[Integer(0),Integer(3)],[Integer(1),Integer(2)], [Integer(1),Integer(2),Integer(3)]])
>>> 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

sage: P = IncidenceStructure([[1,2],[3,4],[2,3]]).packing()                 # needs sage.numerical.mip
sage: sorted(sorted(b) for b in P)                                          # needs sage.numerical.mip
[[1, 2], [3, 4]]
sage: len(designs.steiner_triple_system(9).packing())                       # needs sage.numerical.mip
3

Python

>>> from sage.all import *
>>> P = IncidenceStructure([[Integer(1),Integer(2)],[Integer(3),Integer(4)],[Integer(2),Integer(3)]]).packing()                 # needs sage.numerical.mip
>>> sorted(sorted(b) for b in P)                                          # needs sage.numerical.mip
[[1, 2], [3, 4]]
>>> len(designs.steiner_triple_system(Integer(9)).packing())                       # needs sage.numerical.mip
3

rank()

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

EXAMPLES:

Sage

sage: h = Hypergraph(8, [[0,1,3],[1,4,5,6],[1,2]])
sage: h.rank()
4

Python

>>> from sage.all import *
>>> h = Hypergraph(Integer(8), [[Integer(0),Integer(1),Integer(3)],[Integer(1),Integer(4),Integer(5),Integer(6)],[Integer(1),Integer(2)]])
>>> 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 – boolean (default: False); if True then return a relabeled graph and does not touch self

EXAMPLES:

Sage

sage: # needs sage.schemes
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']]

Python

>>> from sage.all import *
>>> # needs sage.schemes
>>> TD = designs.transversal_design(Integer(5),Integer(5))
>>> TD.relabel({i: chr(Integer(97)+i) for i in range(Integer(25))})
>>> 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']
>>> TD.blocks()[:Integer(3)]
[['a', 'f', 'k', 'p', 'u'], ['a', 'g', 'm', 's', 'y'], ['a', 'h', 'o', 'q', 'x']]

Relabel to integer points:

Sage

sage: TD.relabel()                                                          # needs sage.schemes
sage: TD.blocks()[:3]                                                       # needs sage.schemes
[[0, 5, 10, 15, 20], [0, 6, 12, 18, 24], [0, 7, 14, 16, 23]]

Python

>>> from sage.all import *
>>> TD.relabel()                                                          # needs sage.schemes
>>> TD.blocks()[:Integer(3)]                                                       # needs sage.schemes
[[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 – 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

sage: # needs sage.schemes
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

Python

>>> from sage.all import *
>>> # needs sage.schemes
>>> P4 = designs.projective_plane(Integer(4))
>>> F = designs.projective_plane(Integer(2))
>>> for x in Subsets(P4.ground_set(),Integer(7)):
...     if P4.trace(x,min_size=Integer(2)).is_isomorphic(F):
...         break
>>> subplane = P4.trace(x,min_size=Integer(2)); subplane
Incidence structure with 7 points and 7 blocks
>>> subplane.is_isomorphic(F)
True