# 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 $\lambda$. The positive integer $\lambda$ is called the *index* of the resolution. A resolution with $\lambda = 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 $\lambda$. 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 $\lambda$. When the problem is to find all parallelisms ($\lambda = 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}`

```magma
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_1$ 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_1$ and finding all cliques of size $v/k$ in $G_1$. Any such clique is a parallel class of $D$. The second stage involved building a graph $G_2$ 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_2$. 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$.

## `Example: Resol Parallel (ex-102d24)`

Some of the above functions are illustrated here.

```magma
> 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}
  }
}

```