Setup¶

Once the notebook is started, the package can be imported.

The central class is drg.DRGParameters, which can be given an intersection array in the form of two lists or tuples of the same length.

Instead of an intersection array, parameters $(k, \lambda, \mu)$ for a strongly regular graph or classical parameters $(d, b, \alpha, \beta)$ may also be specified.

The intersection array (given in any of the forms above) may also contain variables. Substitution of variables is possible using the subs method. Note that the diameter must be constant.

Parameter computation¶

As a drg.DRGParameters object is being constructed, its intersection numbers are computed. If any of them is determined to be negative or nonintegral, then an exception is thrown and the construction is aborted. Several other conditions are also checked, for example that the sequences $\{b_i\}_{i=0}^d$ and $\{c_i\}_{i=0}^d$ are non-ascending and non-descending, respectively, and that $b_j \ge c_i$ if $i + j \le d$. The handshake lemma is also checked for each subconstituent. If the graph is determined to be antipodal, then the covering index is also checked for integrality.

The number of vertices, their valency and the diameter of the graph can be obtained with the order, valency, and diameter methods.

The entire array of intersection numbers can be obtained with the pTable method, which returns a drg.Array3D object implementing a three-dimensional array.

The subsets of intersection numbers $\{a_i\}_{i=1}^d$, $\{b_i\}_{i=0}^{d-1}$ and $\{c_i\}_{i=1}^d$ can be obtained as tuples with the aTable, bTable, and cTable methods, respectively. There is also a method intersectionArray returning the entire intersection array as a pair of tuples.

Eigenvalues can be computed using the eigenvalues method. They are sorted in the decreasing order; if there is a variable in the intersection array, then the order is derived under the assumption that the variable takes a (large enough) positive value. If there is more than one variable, a warning is issued that the given ordering is not necessarily correct. This can be avoided by explicitly specifying an order of the variables using the set_vars method (see the DRG-d3-2param.ipynb notebook for an example). The ordering of eigenvalues (and thus the ordering of corresponding parameters) can also be changed later using the reorderEigenvalues method, which accepts an ordering of the indices of the nontrivial eigenvalues (i.e., integers from $1$ to $d$).

Once the ordering of eigenvalues is determined, the cosine sequences and multiplicities of the eigenvalues can be computed using the cosineSequences and multiplicities methods. The multiplicities are checked to be integral.

The eigenmatrix and dual eigenmatrix can be computed using the eigenmatrix and dualEigenmatrix methods. The is_formallySelfDual method checks whether the two matrices are equal (using the current ordering of eigenvalues).

The Krein parameters can be computed using the kreinParameters method, which returns a drg.Array3D object. The Krein parameters are checked to be nonnegative.

Classical parameters can be computed using the is_classical method, which returns a list of all tuples of classical parameters, or False if the graph is not classical.

The method genPoly_parameters returns the tuple $(g, s, t)$ if the parameters correspond to those of a collinearity graph of a generalized $g$-gon of order $(s, t)$, or (False, None, None) if there is no such generalized $g$-gon.

Note that the existence of a strongly regular graph for which $(g, s, t)$ are defined does not imply the existence of a corresponding generalized quadrangle. A distance-regular graph $\Gamma$ of diameter at least $3$ has these parameters defined precisely when $\Gamma$ is isomorphic to the collinearity graph of a corresponding generalized $g$-gon.

All the methods mentioned above store their results, so subsequent calls will not redo the computations. Note that one does not need to call the methods in the order given here - if some required computation has not been done before, it will be performed when needed. Where applicable, the methods above also take three named boolean parameters expand, factor, and simplify (all set to False by default), which control how the returned expression(s) will be manipulated. In the case when there are no variables in use, setting these parameters has no effect.

Parameters of derived graphs¶

In some cases, the parameters of a distance-regular graph imply the existence of another distance-regular graph which can be derived from the original graph. This is true for imprimitive graphs (i.e., antipodal or bipartite), but sometimes, new distance-regular graphs can be obtained by taking subgraphs or by merging classes.

The antipodality of a graph can be checked with the is_antipodal method, which returns the covering index for antipodal graphs, and False otherwise. The parameters of the antipodal quotient of an antipodal graph can then be obtained with the antipodalQuotient method.

The bipartiteness of a graph can be checked with the is_bipartite method. The parameters of the bipartite half of a bipartite graph can then be obtained with the bipartiteHalf method.

In some cases, distance-regularity of the local graph can be established (for instance, for tight graphs). In these cases, the parameters of the local graph can then be obtained with the localGraph method.

Similarly, the distance-regularity of a subconstituent (i.e., a graph induced by vertices at a given distance from a vertex) can be established in certain cases. Their parameters can be obtained using the subconstituent method. Usually, distance-regularity is derived from triple intersection numbers (see below), which are not computed by default. To force this computation, the parameter compute can be set to True.

Note that calling localGraph() is equivalent to calling subconstituent(1). The localGraph method also accepts the compute parameter.

The complement of a strongly regular graph is also strongly regular. If the complement is connected, its parameters can be obtained with the complementaryGraph method.

Sometimes, merging classes of the underlying association scheme yields a new distance-regular graph. Its parameters (or the parameters of a connected component if the resulting graph is disconnected) can be obtained with the mergeClasses method, which takes the indices of classes which will be merged into the first class of the new scheme (i.e., the distances in the original graph which will correspond to adjacency in the new graph).

Note that mergeClasses(2) gives the parameters of the bipartite half for bipartite graphs, and of the complement for non-antipodal strongly regular graphs.

A dictionary mapping the merged indices to parameters of a new graphs for all possibilities can be obtained using the distanceGraphs method.

Feasibility checking¶

To check whether a given parameter set is feasible, the check_feasible method may be called. This method calls other check_* methods which perform the actual checks. Selected checks may also be skipped by providing a parameter skip with a list of strings identifying checks to be skipped.

The following checks are available (see article for a detailed description):

• sporadic: sporadic nonexistence results,
• family: nonexistence results for families of intersection arrays,
• 2graph: checks related to $2$-graphs and Taylor graphs,
• classical: nonexistence results for families of intersection arrays with classical parameters,
• combinatorial: conditions derived from combinatorial arguments,
• conference: checks for conference graphs,
• geodeticEmbedding: checks related to geodetic embeddings,
• 2design: checks related to $2$-designs,
• hadamard: checks related to Hadamard matrices,
• antipodal: checks related to antipodal covers,
• genPoly: checks related to generalized polygons,
• clawBound: claw bound check (Brouwer & Van Lint),
• terwilliger: checks related to Terwilliger graphs,
• secondEigenvalue: checks related to the second largest eigenvalue,
• localEigenvalue: checks related to the eigenvalues of local graphs,
• absoluteBound: absolute bound checking on eigenvalue multiplicities.

After running all the checks described above, the check_feasbile method calls itself on all already derived graphs (antipodal quotient, bipartite half, complement, $2$-graph derivation where applicable), and then also on each parameter set for distance-regular graphs obtained by merging classes. To avoid repetitions, a list of checked intersection arrays is maintained. This step can be skipped by setting the derived parameter to False.

If the parameter set is feasible (i.e., it passes all checks), then check_feasible returns without error. Otherwise, a drg.InfeasibleError exception is thrown indicating the reason for nonexistence and providing a reference.

Details on the given references are available in the drg.references submodule.

Details on the nonexistence may also be extracted from the exception.

Partitions and triple intersection numbers¶

For a given parameter set, the distance partition corresponding to a vertex can be obtained with the distancePartition method, which returns a graph representing the distance partition.

A distance partition corresponding to two vertices can be obtained by passing the distance between them as an argument to distancePartition.

Note that edges are shown between any pair of cells such that their distances from either of the initial vertices differ by at most $1$. To show all the distance partitions corresponding to at most two vertices, the show_distancePartitions may be used (see below).

For a given triple of distances $(U, V, W)$ such that $p^W_{UV} > 0$, the method tripleEquations gives the solution to the system of equations relating triple intersection numbers to the intersection numbers, augmented by equations derived from the Krein condition for each triple $(i, j, h)$ $(1 \le i, j, h \le d)$ such that $q^h_{ij} = 0$. The solution is returned as a drg.Array3D object.

If the solution is not unique, one or more parameters will be present in the solution.

Parameters may also be set explicitly by passing a params argument with a dictionary mapping the name of the parameter to the triple of distances it represents.

If the appropriate triple intersection number is computed to be zero, an edge will not be shown in the distance partition.