Resolutions, Parallelisms and Parallel Classes

Let D be an incidence structure with v points. A resolution of D is a partition of the blocks of D into classes C_i such that each class is a 1-design with v points and index λ. The positive integer λ is called the index of the resolution. A resolution with λ = 1 is called a parallelism. In this case the classes C_i are called parallel classes.

All the functions which deal with resolutions apply to general incidence structures. The functions HasParallelism, AllParallelisms, HasParallelClass, IsParallelClass and AllParallelClasses require that the incidence structure be uniform. The function IsParallelism however applies to a general incidence structure.

HasResolution(D) : Inc -> BoolElt, { SetEnum }, RngIntElt

Return true if and only if the incidence structure D has a resolution. If true, one resolution is returned as the second value of the function and the index of the resolution is returned as the third value.

HasResolution(D, λ) : Inc, RngIntElt -> BoolElt, { SetEnum }

Return true if and only if the incidence structure D has a resolution with index λ. If true, one such resolution is returned as the second value of the function.

AllResolutions(D) : Inc -> SeqEnum

Returns all resolutions of the incidence structure D.

AllResolutions(D, λ) : Inc, RngIntElt -> SeqEnum

Returns all resolutions of the incidence structure D having index λ. When the problem is to find all parallelisms (λ = 1) in a uniform design D, it is best to use the function AllParallelisms described below.

IsResolution(D, P) : Inc, SetEnum[SetEnum] -> BoolElt, RngIntElt

Returns true if and only if the set P of blocks (or sets) is a resolution of the incidence structure D. If true, also returns the index of the resolution as the second value of the function.

HasParallelism(D: parameters) : Inc, RngIntElt -> BoolElt, { SetEnum }

    Al: MonStg                          Default: "Backtrack"

Returns true if and only if the uniform incidence structure D has a parallelism. If true, a parallelism is returned as the second value of the function. The parameter Al allows the user to specify the algorithm used.

Al := "Backtrack": A backtrack search is employed. This is in general very efficient when the design D is parallelizable, irrespective of the number of blocks. In particular, it compares very favourably with the algorithm Clique, described below. The later algorithm is recommended when the design appears to have no parallelism. Backtrack is the default.

Al := "Clique": This algorithm proceeds in two stages. Assume that D has v points and b blocks of size k. Define the graph G₁ of D to be the graph whose vertices are the blocks of D and where two blocks are adjacent if and only if they are disjoint. The first stage of the Clique algorithm involves constructing the graph G₁ and finding all cliques of size v/k in G₁. Any such clique is a parallel class of D. The second stage involved building a graph G₂ of D where the vertices are the parallel classes of D and two parallel classes are adjacent if and only if they are disjoint. The second stage of the Clique algorithm involves searching for cliques of size b/(v/k) in G₂. If such a clique exists then it yields a parallelism of D. (This algorithm was communicated by Vladimir Tonchev).

The clique algorithm is recommended when the design is suspected of having no parallelism. As an example, in the case of a non--parallelizable design with 272 blocks, Clique took around 0.1 second to complete as compared to 2 seconds for the backtrack algorithm. For a non--parallelizable design having 6642 blocks, Clique took around four hours to complete as compared to Backtrack which did not complete in 15 hours. Apart from performing very poorly when D has a parallelism, Clique may require a considerable amount of memory. It is recommended that Backtrack be tried first, and if it does not complete in a reasonable amount of time, then Clique should be used.

AllParallelisms(D) : Inc -> SeqEnum

Returns all parallelisms of the uniform incidence structure D. This function is to be preferred to the function AllResolutions(D, 1) when D is uniform. This is the case since the implementation of AllParallelClasses implies finding cliques in graphs (see the algorithm Clique described in the function HasParallelism), while AllResolutions performs a full backtrack search.

IsParallelism(D, P) : Inc, SetEnum[SetEnum] -> BoolElt, RngIntElt

Returns true if and only if the set P of blocks (or sets) is a parallelism of the incidence structure D.

HasParallelClass(D) : Inc -> BoolElt, { IncBlk }

Returns true if and only if the uniform incidence structure D has a parallel class.

IsParallelClass(D, B, C) : Inc, IncBlk, IncBlk -> BoolElt, { IncBlk }

Returns true if and only if the uniform incidence structure D has a parallel class containing the blocks B and C. If such a parallel class does exist, one is returned as the second value of the function.

AllParallelClasses(D) : Inc -> SeqEnum

Returns all parallel classes of the uniform incidence structure D.

> D := IncidenceStructure< 6 | {1,2,3}, {4,5,6}, {1,3,4}, {2,5,6}>;
> bool, R, lambda := HasResolution(D);
> bool;
true
> R;
{
  { 
    {1, 2, 3},
    {4, 5, 6},
    {1, 3, 4},
    {2, 5, 6}
  }
}
> lambda;
2
> HasResolution(D,2);
true {
  { 
    {1, 2, 3},
    {4, 5, 6},
    {1, 3, 4},
    {2, 5, 6}
  }
}
> AllResolutions(D);
[
  {
    { 
      {1, 2, 3},
      {4, 5, 6},
      {1, 3, 4},
      {2, 5, 6}
    }
  },
  {
    { 
      {1, 2, 3},
      {4, 5, 6}
    },
    { 
      {1, 3, 4},
      {2, 5, 6}
    }
  }
]
> HasParallelism(D);
true {
  { 
    {1, 2, 3},
    {4, 5, 6}
  },
  { 
    {1, 3, 4},
    {2, 5, 6}
  }
}
> V := PointSet(D);
> S := { PowerSet(PowerSet(V)) | 
>        { {1, 2, 3}, {4, 5, 6} }, { {1, 3, 4}, {2, 5, 6} } };
> IsParallelism(D, S);
true
> B := BlockSet(D);
> S := { { B.1, B.2 }, {B.3, B.4 }};
> IsParallelism(D, S);
true
> AllParallelClasses(D);
{
  { 
    {1, 2, 3},
    {4, 5, 6}
  },
  { 
    {1, 3, 4},
    {2, 5, 6}
  }
}