We follow the notation and the terminology of the monograph [BJL99].
An incidence structure is a triple \((V,\mathbf{B},I)\) where \(V\) and \(\mathbf{B}\) are any two disjoint sets and \(I\) is a binary relation between \(V\) and \(\mathbf{B}\), i.e. \(I\subseteq V\times \mathbf{B}\). The elements of \(V\) will be called points, those of \(\mathbf{B}\) blocks and those of \(I\) flags. Instead of \((p, B) \in I\), we will simply write \(p I B\) and use such geometric language as "the point \(p\) lies on the block \(B\)", "\(B\) passes through \(p\)", "\(p\) and \(B\) are incident", etc.
The trace of a block \(B\) is the set \(\{ x \in V : x I B\}\) of the points incident with \(B\). The trace of a point \(p\) is the set \(\{ B \in \mathbf{B} : p I B\}\) of the blocks incident with \(p\). An incidence structure is called simple if the traces of distinct blocks are distinct. For any simple incidence structure, we can (and usually will) identify each block \(B\) with its trace and the incidence relation \(I\) with the membership relation \(\in\).
Let \((V,\mathbf{B},I)\) and label the points as \(p_1,\ldots,p_v\) and the blocks \(B_1,\ldots,B_b\). Then the \(b\times v\) matrix \(M=(m_{ij})\) defined by \(m_{ij}=1\) if \(p_j I B_i\), \(m_{ij}=0\) otherwise, is called the incidence matrix of the structure. The row of \(M\) belonging to a block \(B\) is the incidence vector of \(B\).
Let \((V,\mathbf{B},I)\) and \((V',\mathbf{B}',I')\) be incidence structures and let \(\pi:V\cup \mathbf{B} \to V'\cup \mathbf{B}'\) be a bijection. \(\pi\) is called an isomorphism if and only if it satisfies:
\(V^\pi =V'\) and \(\mathbf{B}^\pi =\mathbf{B}'\);
\(p I B \Leftrightarrow p^\pi I' B^\pi\) for all \(p\in V\) and \(B\in \mathbf{B}\).
In this case, the two incidence structures are said to be isomorphic. If \((V,\mathbf{B},I)=(V',\mathbf{B}',I')\), then \(\pi\) is called an automorphism.
‣ IsIncidenceStructure( object ) | ( filter ) |
Returns: true or false
A GAP category of abstract incidence structures.
‣ IncidenceStructureByIncidenceMatrix( pts, bls, incmat ) | ( function ) |
Returns: The incidence structure object corresponding to the set pts of points and the list bls of blocks and the incidence matrix incmat. incmat must be a boolean matrix with |bls| rows and |pts| columns.
‣ IncidenceStructureByIncidenceMatrixNC( pts, bls, incmat ) | ( function ) |
The non-checking version of the command IncidenceStructureByIncidenceMatrix.
‣ IncidenceStructureByBlocks( pts, bls ) | ( function ) |
Returns: The incidence structure object corresponding to the set pts of points and the list bls of blocks. The elements of bls must be subsets of pts.
‣ IsIndexBasedIncidenceStructure( s ) | ( attribute ) |
We call the incident structre s index based if its set of points is the integer range [1..n] and blocks are subsets of [1..n].
‣ IsSimpleIncidenceStructure( s ) | ( attribute ) |
Returns: true if s is a simple incident structure.
An incident structure is said to be simple if each block is uniquely determined by the set of points which are incident with it.
‣ InfoIncidenceStructures | ( info class ) |
An infoclass for the package. Its default value is \(0\).
‣ PointsOfIncidenceStructure( s ) | ( attribute ) |
Returns: The list of points of the incidence structure s.
‣ BlocksOfIncidenceStructure( s ) | ( attribute ) |
Returns: The list of blocks of the incidence structure s.
‣ TraceOfPoint( s, pt ) | ( operation ) |
Returns: The list of blocks which are incident with pt in the incidence structure s.
‣ TraceOfBlock( s, bl ) | ( operation ) |
Returns: The list of points which are incident with bl in the incidence structure s.
‣ AutomorphismGroup( s ) | ( attribute ) |
Returns: The automorphism group of the incidence structure s.
The function computes the automorphism group of s with the help of its incidence digraph.
‣ HashValue( s ) | ( attribute ) |
Returns: The hash value of the incidence structure s.
The function computes the value of s with the help of canonical labeling of its incidence digraph.
‣ Isomorphism( s1, s2 ) | ( operation ) |
Returns: An isomorphism between the incidence structures s1 and s1 if they are isomorphic, and fail otherwise.
The isomorphism is a bijection between the points sets and between the line sets of the incidence structures \(S_1\) and \(S_2\) such that the incidence relations are preserved. In this implementation, an isomorphism is given by a permutation \(\beta\) of degree \(n+m\), where \(n\) is the number of points and \(m\) is the number of lines. The bijections defined by \(\beta\) are \(p[i]\mapsto p'[i^\beta]\) and \(b[j] \mapsto b'[(j+n)^\beta-n]\), where \(p[i]\), \(p'[i']\) are points and \(b[j]\), \(b'[j']\) are blocks of \(S_1\), \(S_2\), respectively.
Canonocal labellings, automorphisms and isomorphisms of incidence structures are computed with the help of their incidence graphs, which is are bipartite graphs with upper vertices the points and lower vertices the blocks. The computation is done using the GAP package BlissInterface [Nag19].
gap> LoadPackage("IncidenceStructures",false); true gap> s:=IncidenceStructureByBlocks([1..3],[[1],[1,2],[1,2,3]]); <Incidence structure on 3 points> gap> PointsOfIncidenceStructure(s); [ 1, 2, 3 ] gap> BlocksOfIncidenceStructure(s); [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] gap> CanonicalLabellingOfIncidenceStructure(s); (1,3) gap> KnownAttributesOfObject(s); [ "AutomorphismGroup", "IsIndexBasedIncidenceStructure", "PointsOfIncidenceStructure", "BlocksOfIncidenceStructure", "CanonicalLabellingOfIncidenceStructure" ] gap> s:=IncidenceStructureByIncidenceMatrix( [1..4], "abcdef", > [[true,true,false,false], > [true,false,true,false], > [true,false,false,true], > [false,true,true,false], > [false,true,false,true], > [false,false,true,true]] > ); <Incidence structure on 4 points> gap> TraceOfPoint(s,2); "ade" gap> TraceOfBlock(s,'c'); [ 1, 4 ] gap> SetInfoLevel(InfoIncidenceStructures,1); gap> CanonicalLabellingOfIncidenceStructure(s); #I BLISS_BIPARTITE_CANONICAL_LABELING called (1,4)(2,3)(5,10,9)(6,8) gap> StructureDescription(AutomorphismGroup(s)); "S4" gap> SetInfoLevel(InfoIncidenceStructures,2); gap> t:=IncidenceStructureByBlocks( "rozi", > ["or","iz","rz","oi","ir","oz"] ); <Incidence structure on 4 points> gap> Isomorphism(s,t); #I BLISS_BIPARTITE_CANONICAL_LABELING called #I <outneigh> parameter for BLISS command: [ [ 2, 3 ], [ 1, 4 ], [ 3, 4 ], [ 1, 2 ], [ 1, 3 ], [ 2, 4 ] ] #I <iso>: ( 1, 3, 4)( 6, 7, 9, 8,10) (1,3,4)(6,7,9,8,10) gap> HashValue(s); 4078249033 gap> HashValue(t); 4078249033 gap> StructureDescription(AutomorphismGroup(t)); "S4"
generated by GAPDoc2HTML