On the Spectrum of Minimal Covers By Triples
Except where reference is made to the work of others, the work described in this
dissertation is my own or was done in collaboration with my advisory committee. This
dissertation does not include proprietary or classifled information.
Vincent Edward Castellana
Certiflcate of Approval:
C.C. Lindner
Distinguished University Professor
Mathematics and Statistics
Dean Hofiman, Chair
Professor
Mathematics and Statistics
Peter D. Johnson Jr.
Professor
Mathematics and Statistics
Luc Teirlinck
Professor
Mathematics and Statistics
Nels Madsen
Associate Professor
Mechanical Engineering
Stephen L. McFarland
Dean
Graduate School
On the Spectrum of Minimal Covers By Triples
Vincent Edward Castellana
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
August 7, 2006
On the Spectrum of Minimal Covers By Triples
Vincent Edward Castellana
Permission is granted to Auburn University to make copies of this dissertation at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Dissertation Abstract
On the Spectrum of Minimal Covers By Triples
Vincent Edward Castellana
Doctor of Philosophy, August 7, 2006
(M.S., Western Michigan University, 2001)
(B.S., SUNY at Fredonia, 1994)
41 Typed Pages
Directed by Dean Hofiman
A Minimal Cover by Triples is an ordered pair (V;T) where V is a flnite set and T
is a collection of three element subsets of V with two properties. First, that every pair of
elements of V appear together in at least one element of T. Second, if any element of T
is removed the flrst property no longer holds. In this dissertation we explore the possible
values jTj can take on for a given jVj. In addition, construction techniques are given to
construct a Minimal Cover by Triples for given values of jVj and jTj.
iv
Acknowledgments
I would like to thank my Wife Christine and children Devin, Arista, and Olivia for
being my main inspiration and motivation during this project.
I would also like to thank my parents Tom and Joan for giving me the foundation and
continued support to make my success in graduate school possible.
I would also like to thank my advisor Dean Hofiman for his wonderful guidance, en-
couragement and patience.
I would like to thank Olivia Knight and Karl Weber for providing the most important
thing in my life.
I would like to thank my committee and the Faculty members of both Auburn Univer-
sity and Western Michigan University who helped me along with my graduate studies.
I would like to thank Michael Raines for his helpful advice and encouragement.
v
Style manual or journal used Journal of Approximation Theory (together with the style
known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally LATEX)
together with the departmental style-flle aums.sty.
vi
Table of Contents
List of Figures viii
1 Introduction 1
2 The Max, the Min and the Missing. 3
2.1 The Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Solving the Mystery of the Missing Value . . . . . . . . . . . . . . . . . . . 4
3 Needed Constructions 7
3.1 Minimum cover when v ? 0 mod 6 . . . . . . . . . . . . . . . . . . . . . . 7
3.2 One more triple than a minimum cover when v ? 1 or 3 mod 6 . . . . . . 8
3.3 One more triple than a minimum cover when v ? 2 or 4 mod 6 . . . . . . 10
3.4 Minimum cover when v ? 5 mod 6 . . . . . . . . . . . . . . . . . . . . . . 11
4 proof of Main Theorem 12
4.1 v ? 0 mod 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 v ? 1 or 3 mod 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 v ? 2 or 4 mod 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.4 v ? 5 mod 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 Imbrical Design Flaws 24
5.1 The basic augmentation procedure . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 The Proof of the Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . 27
Bibliography 28
Appendices 29
A Some Specific MCT?s 30
A.1 (9;13) MCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
A.2 (13;27) MCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
A.3 (15;36) MCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
B v = 5;7 or 8 31
B.1 v = 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
B.2 v = 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
B.3 v = 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
vii
List of Figures
2.1 An example of a graph with exactly one cycle of length 6 . . . . . . . . . . 5
2.2 Narrowing down G when b = ?v?12 ??1 . . . . . . . . . . . . . . . . . . . . . 6
3.1 Handling the common edges . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Building a (13;27) MCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Building a (15;36) MCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
viii
Chapter 1
Introduction
We will refer to the ordered pair (V;T) as a Collection of Triples (CoT) whenever V is
a flnite non{empty set and T is a collection of three element subsets of V. The elements of
T will be referred to as triples. A Steiner Triple System is a CoT (V;T) with the additional
property that every pair of elements of V appears together in exactly one triple of T. It is
well known that a Steiner Triple System exists on V if and only if jVj? 1 or 3 mod 6.
The natural next question of how close you can come is also well known in two forms.
One can look at maximum packings or minimum covers. A Packing of Triples is a CoT
(V;T) with the property that every pair of elements of V appears together in at most one
triple of T. A Packing of Triples (V;T) is a maximum packing if for every other Packing
of Triples (V;T0) we have that jT0j ? jTj. A Cover by Triples is a CoT (V;T) with the
property that every pair of elements of V appears together in at least one triple of T. A
Cover by Triples (V;T) is a minimum cover if for every Cover by Triples (V;T0) we have
that jTj?jT0j. More detailed information on maximum packings and minimum covers can
be found in [1].
The purpose of this document is to take the idea of minimum covers one step further
and look at minimal covers. A Minimal Cover by Triples (MCT) is a cover by triples, (V;T)
, with the property that if you remove any triple from T you no longer have a cover by
triples. If (V;T) is a MCT with jVj = v and jTj = b then we call it a (v;b) MCT
1
We will address speciflcally how many triples can be in a minimal cover by triples for
a given value for v. An attempt, albeit unsuccessful, to do so (as well as for block size 4) is
made in [2]. In chapter 5 of this document we will look at that particular attempt.
We state our main claim, which will be proved in this discourse, as follows:
Theorem 1.1 There is a (v;b) MCT if and only if
?v
3
?v ?1
2
??
? b ?
 v ?1
2
?
?2, or b =
 v ?1
2
?
(1.1)
with the following exceptions:
1. there is a (5;5) MCT
2. there is no (7;8) MCT
2
Chapter 2
The Max, the Min and the Missing.
The lower bound of equation 1.1 is well known and can be obtained from information
found in [1] where there is a section devoted to minimum covers with triples. The upper
bound and missing value will be dealt with in this chapter.
2.1 The Upper Bound
It is often useful to consider this problem in graph theoretical terms. If we consider
our minimal cover to be a cover of the complete graph with v vertices using copies of K3 we
can use this notion to help prove the upper bound. With this in mind we will refer to any
edge that appears in exactly one triple of the cover to be a unique edge and any edge that
appears in at least two triples of the cover will be called a common edge. In any minimal
cover each triple will have at least one unique edge. Choose a unique edge from each triple
and denote those edges as special edges.
Note that each triple then has one special edge and two non{special edges. We also
consider the fact that each non{special edge can appear in at most v ?2 triples. Thus we
have b special edges and at least 2bv?2 non special edges giving us that
b+ 2bv ?2 ?
 v
2
?
: (2.1)
3
Applying some algebra to that gets us
b ?
 v ?1
2
?
(2.2)
To show that this bound is sharp, simply choose your favorite point of V, name it 1,
and let T = ff1;u;vgju 6= v; u;v 2 V nf1gg:
2.2 Solving the Mystery of the Missing Value
Possibly the most interesting result that contributes to the main theorem is the follow-
ing:
Theorem 2.1 There exists a (v;?v?12 ??1) MCT if and only if v = 5.
If we let V = f0;1;2;3;4g and T = ff0;1;3g;f1;2;4g;f2;3;0g;f3;4;1g;f4;0;2gg, then
we have a (5;5) MCT. So it remains to be shown that one can?t be obtained if v 6= 5.
Suppose (V;T) is a (v;b) MCT. As in section 2.1 we will choose one unique edge of
each triple in T and label it as a special edge all other edges will be considered non{special
edges. Let G be the subgraph of Kv induced by the set of non{special edges. Note that
jE(G)j = ?v2??b.
For each x;y 2 V with x 6= y and xy 62 E(G) there is a path Pxy of length 2 from x
to y in G. Since xy is not in G it was a special edge so we will take the non{special edges
from the triple it appears in to make up the path Pxy. If you deflne the path Pxy in such a
way, it guarantees that each edge of G is in at least one Pxy.
With the existence of all the Pxy?s we have that every pair of vertices are either adjacent
or distance 2 apart in G. Hence the diameter of G is 2 and it is connected. It also follows
4
Figure 2.1: An example of a graph with exactly one cycle of length 6
that v?1 ?jE(G)j thus b ??v2??(v?1) = ?v?12 ?. (A fact that we have previously proved
in section 2.1.)
Suppose that b = ?v?12 ??1. Then we have that jE(G)j = v and it follows that removing
any edge of G either disconnects it or makes it acyclic. Hence G contains exactly one cycle
of some length k. See flgure 2.1 for an example of such a graph. If we were to remove the
edges of the cycle from G, we would be left with a forest. We will refer to this forest as the
fringe of G. So let?s consider what possible values we can have for k.
If k ? 6, then G would have diameter of at least 3; hence k < 6. Suppose k = 5 or 4, if
there is a fringe edge then again the diameter will be at least 3 so in this case G can only be
a cycle. If k = 3 and the fringe is anything other than a star then the diameter will again
be at least 3. So the possible forms of G will be as in flgure 2.2.
If k = 3 then there is no way for edge y1y2 to be in any Pxy so k 6= 3. If k = 4 then we
will have Pxz and Pwy. Without loss of generality, assume that Pxz is the path xyz. If Pwy
is the path wxy then the edge wz is in no Pxy and if Pwy is the path wzy then the edge wx
is in no Pxy. So it follows that k 6= 4. Thus if b = ?v?12 ??1 then v = 5.
5
x
w y
z
x1
x2 xv-3
z
y1 y2
k=3 k=4 k=5
Figure 2.2: Narrowing down G when b = ?v?12 ??1
6
Chapter 3
Needed Constructions
3.1 Minimum cover when v ? 0 mod 6
We will make use of the \1{factor covering Construction" found in [1]. It will be used
not only as the way to obtain the minimum number of triples in its respective case but as
a starting point to obtain most of the other possible amounts of triples. The construction
makes use of a pairwise balanced design with one block of size 5 and the rest of size 3. A
pairwise balanced design (or PBD for short) is an ordered pair (X;B) were X is a flnite
nonempty set and B is a collection of subsets of X, called blocks, with the property that
every pair of elements of X appears in exactly one block of B. How to construct the required
PBD for the 1{factor covering construction is also found in [1].
We reproduce the 1{factor covering construction here with a few minor changes to how
things are labeled.
Construction 3.1 (The 1{factor covering Construction)
Let v = 6n and let (X;B) be a PBD of order v ? 1 with one block fd;e;f;x0;y0g
of size 5 and the remaining blocks of size 3. Denote by T the collection of blocks of size
3. Let S = f1g[X and let ? = ffx1;y1g;fx2;y2g;:::;fx3n?3;y3n?3gg be any partition
of X n fd;e;f;x0;y0g. Let ?(1) = ff1;x1;y1g;f1;x2;y2g;:::;f1;x3n?3;y3n?3gg and
F(1) = ff1;d;fg;f1;e;fg;f1;x0;y0g;fx0;y0;fg;fd;e;x0g;fd;e;y0gg. Then (S;T?) is
a minimum covering of order v where T? = T [?(1)[F(1).
7
d
ef
1
2
34
5
6
Figure 3.1: Handling the common edges
3.2 One more triple than a minimum cover when v ? 1 or 3 mod 6
We will denote the multigraph obtained by taking all the edges of the triples of the
cover as the cover graph. Every vertex of this graph will be of even degree. When v ? 1 or 3
mod 6 the cover graph for a minimum cover is the complete graph. So if we are interested
in one more triple than there is in a minimum cover the associated cover graph will be a
complete graph plus three extra edges. Since a complete graph with v ? 1 or 3 mod 6 has
even degree it follows that the extra edges must form a K3. The only way to do this and
have a minimal cover is for no two of the three common edges to appear in a triple together.
This forces us to have the structure in flgure 3.1. Since this requires at least nine vertices
it follows that we can not have a (7;8) MCT.
If we are looking to obtain a (9;13) MCT we can flrst add the triples fd;3;4g, fe;5;6g
andff;1;2gto what we have in flgure 3.1. For future reference we will refer to this collection
of triples as fi. What we are then left with is the edges of a K6 minus a matching (denoted
8
K3
K M6- K4
K3,4
K6,4
Figure 3.2: Building a (13;27) MCT
as K6 ?M for brevity here on) which can easily be partitioned into triples. An example of
a (9;13) MCT can be found in Appendix A.1.
In order to obtain a (13;27) MCT we again start with fi. What remains is the graph
we have in flgure 3.2. We then 3 edge color the K4 using the vertex labels of the K3 as
colors and we 4 edge color the K6 ?M using the vertex labels of the K4 as colors. Then
for each edge fu;wg of either the K4 or K6 ?M we add the triple fu;w;cg where c is the
color of fu;wg. An example of a (13;27) MCT constructed in such a manner can be found
in Appendix A.2.
To obtain a (15;36) MCT we again start with fi after which we are left with the graph
in flgure 3.3. This time we will need to make use of an equitable edge coloring. For our
purposes, an edge coloring is equitable if for any two colors i and j the number of edges
colored i is equal to the number of edges colored j. We then 6 edge color the K6 ? M
equitably, using the vertex labels of the K6 as colors, in such a way that the color pairs
missing at each vertex form a 2{regular subgraph of the K6 when taken as edges. We will
call this 2{regular subgraph G. Next we 3 edge color the K6?G using the labels of the K3
9
K3
K M6- K6
K3,6
K6,6
Figure 3.3: Building a (15;36) MCT
as colors. For each edge fu;wg that has been colored we add the triple fu;w;cg where c is
the color of the edge. Finally for each edge fu;wg of G if x is the vertex of the K6?M that
has no edge colored u or w then add the triple fu;w;xg. An example of a (15;36) MCT
constructed in such a manner can be found in Appendix A.2.
For any v ? 1 or 3 mod 6 with v > 18 we can start by embedding any STS(9) in a
STS(v) using the process found in [3]. Replacing the triples of the STS(9) with the triples
of our (9;13) MCT will give us a (v; v(v?1)6 +1) MCT.
3.3 One more triple than a minimum cover when v ? 2 or 4 mod 6
We are going to make use of a modifled version of the \tripole covering Construction"
a minimum cover for these orders found in [1]. Instead of starting with a Steiner triple
system of order v ?1 we will start with the minimal cover (V0;T0) of order v ?1 with one
extra triple constructed in section 3.2. We begin by renaming the elements of V0. Choose
any triple of T0 that does not contain any of the points d;e;f;2;4 or 6 and rename its points
10
u;s and w. Let a = x1, b = x2, c = x3, 2 = y3, 4 = y1, 6 = y2. The remaining points
rename in any fashion with the labels x4;:::;x1
2v?2
;y4;:::;y1
2v?2
.
Once we have renamed the points we let V = V0 [ f1g construct T in the follow-
ing manner. Let A be all the triples of T0 n ffu;s;wgg (properly renamed); let B =
ff1;u;sg;f1;s;wg;f1;u;wgg; let C = ff1;xi;yigj1 ? i ? 12v ? 2g. Finally T =
A[B [C. We then have the desired MCT.
3.4 Minimum cover when v ? 5 mod 6
We will be making use of the \double edge covering Construction" found in [1].
Construction 3.2 (The double edge covering Construction)
Let v = 6n+5 and let (S;B) be a PBD of order v with one block fa;c;d;e;fg of size
5 and the remaining blocks of size 3. Denote by T the collection of blocks of size 3, and let
T? = ffa;f;cg;fa;f;dg;fa;f;eg;fc;d;egg. Then (S;T [T?) is a minimum cover by triples
of order v.
11
Chapter 4
proof of Main Theorem
The techniques we will use to construct minimal covers for all possible values of b will
start with a MCT with either the least possible number of triples or one more than the
least possible. It will entail choosing one special point (akin to choosing the point in the
construction of a MCT with the largest possible number of triples). Then in a strategic
manner we will remove triples that don?t contain the special point. For each unique edge
from a triple that has been removed we will add a triple containing that edge and the special
point. When we do this the only edges we cause to become duplicated are edges incident
to the special point. The only danger in this is if there are triples whose unique edges are
incident to the special point. In the cases where this is a problem we will carefully remove
triples in a manner that will not cause those critical unique edges to be duplicated until
after the common edge of the triple they are in has become a unique edge.
4.1 v ? 0 mod 6
Let v = 6n, n ? 1. The minimum value, 6n2, can be obtained using construction 3.1.
To get the remaining values we will next separate the triples of this initial minimal cover
into 4 classes. For notational purposes if we are referring to a vertex xi or yi and it is not
important whether it is an x or a y but the subscript is important we will refer to it as zi.
We categorize the triples as follows:
Type 0 The triples f1;e;fg, f1;d;fg and the triples of the form f1;xi;yig for 0 ? i ?
3n?3.
12
Type 1 The triple fx0;y0;fg and the triples of the form fxi;yi;vig where 1 ? i ? 3n?3 and
vi is the third element of the triple containing xi and yi but not 1.
Type 2 Any triple of the form fzi;zj;zkg where 0 ? i < j < k ? 3n?3 and any triple of the
form fu;zi;zjg where u 2fd;e;fg and 1 ? i < j ? 3n?3
Type 3 The triples fd;e;x0g and fd;e;y0g
Obviously we have 3n Type 0, 3n ? 2 Type 1 and 2 Type 3 triples; which leaves us
6n2 ?6n Type 2 triples. We now proceed to show how to use this starting point as a way
to construct a minimal cover with b triples for all b, 6n2 < b < 18n2 ?9n.
We also want to take note that the Type 0 triples of the form f1;xi;yig have unique
edges that are adjacent to inflnity. Each one shares the edge fxi;yig with a Type 1 triple.
So we need to take care how we remove triples until all the Type 1 triples are removed.
If b ? 6n2 +3n?2 it can be obtained simply by removing b?6n2 type one triples and
replacing them with new triples in the following manner:
1. Remove the triple fx0;y0;fg and replace it with the triples f1;x0;fg and f1;y0;fg.
2. Set i = 1.
3. Remove the Type 1 triple fxi;yi;vig and replace it with the triples f1;xi;vig and
f1;yi;vig.
4. If vi = zj for some j and the type 1 triple containing xj and yj has not been removed
yet set i = j otherwise set i to the lowest possible value such that fxi;yi;vig has not
been removed.
13
5. Go to step 3 unless we now have enough triples or there are no more Type 1 triples
left.
When we remove the triple fxi;yi;vig with vi = zj and if fxj;yj;vjg has not yet been
removed we are in danger of causing a triple to contain no unique edges. Assume without
loss of generality that vi = xj. At this point in the Type 0 triple f1;xj;yjg the only unique
edge is f1;yig. If there is also a Type 1 triple fxk;yk;vkg where vk = yj and we remove it
and add the corresponding triples it will result in the triple f1;xj;yjg no longer having a
unique edge and hence we no longer have a MCT. If we flrst remove the triple fxj;yj;vjg
we can avoid this problem. This is the reason for step 4 being as it is.
We need not worry about the removal of a single Type 1 triple causing a problem. The
removal of fxi;yi;vig with vi = zj (without loss of generality assume zj = xj) can only
cause the edges f1;xig , f1;yig , and f1;xjg to be come common edges. This isn?t a
problem because fxi;yig has just become a unique edge and if f1;yjg is common then the
triple fxj;yj;vjg would have previously been removed so fxj;yjg will be a unique edge.
Ifb > 6n2+3n?2weflrstremoveandreplaceallthetype1triplesintheabovedescribed
manner. We then choosebb?(6n2+3n?2)2 ctype 2 triples. For each such triplefu;v;wgchosen,
we remove it and replace it with the triples f1;u;vg,f1;v;wg and f1;u;wg. If we now
have a system containing b triples we are done, otherwise we have one containing b ? 1
triples and then remove the triple fd;e;x0g and replace it with the triples f1;x0;dg and
f1;x0;eg.
Example 4.1 (v = 18;b = 66)
Suppose we wish to construct a (18;66) MCT. Lets start with V = fd;e;f;x0;x1;:::;x6;
y0;y1;:::;y6g and T contain the following triples:
14
Type 0 f1;d;fg, f1;e;fg, and f1;xi;yig for all i, 0 ? i ? 6;
Type 1 fx0;y0;fg, fx1;y1;x3g, fx2;y2;y3g, fx3;y3;y6g, fx4;y4;x5g, fx5;y5;y2g,
fx6;y6;x1g;
Type 2 fx0;x3;x5g, fx0;y3;x1g, fx0;y5;y1g, fx0;x4;x6g, fx0;y4;x2g, fx0;y6;y2g,
fy0;x5;x1g, fy0;y3;y5g, fy0;x4;y1g, fy0;x6;x2g, fy0;y4;y6g, fy0;x3;y2g,
fd;x3;x6g, fd;y3;x5g, fd;x4;y6g, fd;y4;y5g, fd;x1;y2g, fd;y1;x2g, fe;x5;x2g,
fe;y5;x1g, fe;x6;y2g, fe;y6;y1g, fe;x3;y4g, fe;y3;x4g, ff;x1;y4g, ff;y1;y3g,
ff;x2;x3g, ff;y2;x4g, ff;x5;y6g, ff;y5;x6g, fx3;x4;y5g, fx5;x6;y1g,
fx4;x1;x2g, fy3;y4;x6g, fy5;y6;x2g, fy4;y1;y2g;
Type 3 fd;e;x0g and fd;e;y0g.
So we are starting with b = 54. First we must remove the Type 1 triples. So lets
start by removing fx0;y0;fg and replacing it with f1;x0;fg and f1;y0;fg. Next we
remove fx1;y1;x3g and replace it with f1;x1;x3g and f1;y1;x3g. At this point we are
supposed to set i = 3 but let us consider what happens if we don?t bother to and just remove
fx2;y2;y3g and replace it with f1;x2;y3g and f1;y2;y3g. If we do that T now has as a
subset ff1;x1;x3g;f1;x2;y3g;f1;x3;y3g;fx3;y3;y6gg which means that f1;x3;y3g has
no unique edge.
So let us proceed as we are supposed to and set i = 3 and then remove fx3;y3;y6g
and replace it with f1;x3;y6g and f1;y3;y6g. Next we need to set i = 6 and then
remove fx6;y6;x1g and replace it with f1;x6;x1g and f1;y6;x1g. This time, since we
have already removed fx1;y1;x3g, we set i = 2. We then remove fx2;y2;y3g and replace it
with f1;x2;y3g and f1;y2;y3g. Next we set i = 4 and remove fx4;y4;x5g and replace it
15
with f1;x4;x5g and f1;y4;x5g. Finally we set i = 5 and remove fx5;y5;y2g and replace
it with f1;x5;y2g and f1;y5;y2g.
At this point we now have b = 61 so we need to add flve more triples. Dividing by
two and rounding down tells us to pick two Type 2 triples for removal. So lets remove
fx0;x3;x5g and fx0;y3;x1g. We replace them with f1;x0;x3g, f1;x3;x5g, f1;x0;x5g,
f1;x0;y3g, f1;y3;x1g, and f1;x0;x1g. At this point we now have b = 65, so flnally we
remove fd;e;x0g and replace it with f1;x0;dg and f1;x0;eg. So following this process
we have constructed an (18;66) MCT.
4.2 v ? 1 or 3 mod 6
We will cover all possibilities with v ? 9, the case when v = 7 will be handled separately
in section B.2. Assume v = 6n + 1 with n ? 2 or that v = 6n + 3 with n ? 1. A Steiner
Triple System of order v is a minimum cover by triples in this case [1]. We will obtain the
rest of the values in the range by starting with the (v; v(v?1)6 + 1) MCT we constructed in
section 3.2 and building larger covers by replacing select triples with multiple replacement
triples.
Noting that V = fd;e;f;1;2;:::;v ?3g and fi ? T, we will start by categorizing the
triples in the following manner:
Type 0 All triples of T of the form fd;u;wg where u;w 2 V ?fdg,
Type 1 The triples fe;f;3g and fe;f;4g,
Type 2 All triples of T of the form fx;y;ug where x;y 2 V ?fd;e;fg and u 2 V ?fdg.
16
It follows that we have v+12 Type 0 triples and 2 Type 1 triples. Thus it leaves us either
6n2?2n?2 or 6n2+2n?2 Type 2 triples depending on if v = 6n+1 or 6n+3 respectively.
We see that in this case, none of the Type 0 triples are lacking a unique edge that is
not incident to d so the construction process will be much less complicated. Suppose we
want to construct a (v;b) MCT where v(v?1)6 + 1 < b < (v?1)(v?2)2 ? 1. First we choose6
66
4b?
?v(v?1)
6 +1
?
2
77
75 type 2 triples. For each such triple fx;y;ug chosen we remove it and
replace it with the triplesfd;x;yg, fd;y;ugandfd;u;xg. At this point our T either contains
b or b?1 triples. In the flrst case we are done, otherwise we simply remove the triplefe;f;3g
and replace it with the triples fd;e;3g and fd;f;3g.
Example 4.2 (v = 9;b = 20)
Suppose we wish to construct a (9;20) MCT. Lets start with the (9;13) MCT from
section A.1. Categorizing the triples we have:
Type 0 fd;e;1g, fd;e;2g, fd;f;5g, fd;f;6g,and fd;3;4g;
Type 1 fe;f;3g and fe;f;4g;
Type 2 fe;5;6g, ff;1;2g, f1;3;5g, f1;4;6g, f2;3;6g, and f2;4;5g.
We need to add 7 triples, so we start by removing 3 Type 2 triples. Let?s remove
fe;5;6g, ff;1;2g, and f1;3;5g. Next we replace them with the triples fd;e;5g,fd;e;6g,
fd;5;6g, fd;f;1g, fd;f;2g, fd;1;2g, fd;1;3g, fd;1;5g, and fd;3;5g. At this point we have
a (9;19) MCT. All we need to do is remove fe;f;3g and replace it with fd;e;3g and fd;f;3g
giving us a (9;20) MCT.
17
4.3 v ? 2 or 4 mod 6
We will cover all possibilities with v ? 10, the case when v = 8 will be handled
separately in section B.3. When v = 4 the results are trivial as
?4
3
?3
2
??
=
 3
2
?
. Assume
v = 6n+2 with n ? 2 or that v = 6n+4 with n ? 1. A construction for a minimum cover
with b = 13
?
v2
2 +1
?
(which is 6n2+4n+1 or 6n2+8n+3 respectively) can be found in [1].
We will make use of the construction from section 3.3 that creates a MCT with one extra
triple as a starting point.
We categorize the triples in the following manner:
Type 0 The triples f1;u;sg, f1;u;wg, f1;s;wg and all triples of the form f1;xi;yig for
all i, 1 ? i ? 12v ?2;
Type 1 the triples of the form fxi;yi;fiig for all i, 1 ? i ? 12v ?2 where fii 2 V nfxi;yi;1g;
Type 2 the triples of the form fzi;zj;zkg or fzi;zk; g where 1 ? i < j < k ? 12v ? 2 and
 2fu;s;wg except for the triples described in the next type;
Type 3 The triples fx1;x2;y3g, fx1;x2;fl1g, fx2;x3;y1g, fx2;x3;fl3g, fx1;x3;y2g and
fx1;x3;fl5g where fli is the point that i was renamed to in section 3.3.
We are starting with a total of 6n2 + 4n + 2 (or 6n2 + 8n + 4 if v = 6n + 4) triples.
Clearly there are 3n + 2 (or 3n + 3) Type 0 , 3n?1 (or 3n) Type 1 and 6 Type 3 triples;
which leaves us with 6n2 ? 2n ? 5 (or 6n2 + 2n ? 5) Type 2 triples. We now proceed to
show how to use this starting point as a way to construct a minimal cover with b triples for
all b, 6n2 +4n+2 < b < 18n2 +3n?1 (or 6n2 +8n+4 < b < 18n2 +15n+2).
18
If b ? 6n2 + 7n + 1 (or b ? 6n2 + 11n + 4) it can be obtained simply by removing
b?(6n2+4n+2) (or b?6n2+8n+4) type one triples and replacing them with new triples
in the following manner:
1. Set i = 1.
2. Remove the Type 1 triple fxi;yi;fiig and replace it with the triples f1;xi;fiig and
f1;yi;fiig.
3. If fii = zj for some j and the type 1 triple containing xj and yj has not been removed
yet set i = j otherwise set i to the lowest possible value such that fxi;yi;fiig has not
been removed.
4. Go to step 2 unless we no longer need any additional triples or there are no more
Type 1 triples to remove.
As in the construction in section 4.1 we have to take care while removing triples if there
are still Type 1 triples. Thus we have taken similar precaution in our algorithm for their
removal.
If 6n2 +7n+1 < b ? 18n2 +3n?9 (or 6n2 +11n+4 < b ? 18n2 +15n?6) we flrst
remove and replace all the type 1 triples in the above described manner. We then choose
bb?(6n2+7n+1)2 c (or bb?(6n2+11n+4)2 c) type 2 triples. For each such triple fp;q;rg chosen,
we remove it and replace it with the triples f1;p;qg,f1;q;rg and f1;p;rg. If we now
have a system containing b triples we are done, otherwise we have one containing b ? 1
triples and then remove the triple fx1;x2;y3g and replace it with the triples f1;y3;x1g
and f1;y3;x2g.
19
If b > 18n2 +3n?9 (or b > 18n2 +15n?6) we flrst remove all Type 1 triples followed
by all Type two triples using the methods described above. At this point the number of
triples we need to add is between 1 and 7, let this number be b0. We then add the remaining
number of triples in the following manner:
if b0 = 1, remove fx1;x2;y3g and replace it with f1;y3;x1g and f1;y3;x2g;
if b0 = 2, proceed as if b0 = 1 and then remove fx1;x3;y2g and replace it with f1;y2;x1g and
f1;y2;x3g;
if b0 = 3, proceed as if b0 = 1 and then remove fx1;x2;fl1g and replace it with f1;x1;x2g,
f1;x1;fl1g and f1;x2;fl1g;
if b0 = 4, proceed as if b0 = 3 and then remove fx1;x3;y2g and replace it with f1;y2;x1g and
f1;y2;x3g;
if b0 = 5, proceed as if b0 = 4 and then remove fx2;x3;y1g and replace it with f1;y1;x2g and
f1;y1;x3g;
if b0 = 6, proceed as if b0 = 4 and then remove fx1;x3;fl5g and replace it with f1;x1;x3g,
f1;x1;fl5g and f1;x3;fl5g;
if b0 = 7, proceed as if b0 = 6 and then remove fx2;x3;y1g and replace it with f1;y1;x2g and
f1;y1;x3g.
Example 4.3 (v = 10;b = 30)
Suppose we wish to construct a (10;30) MCT. We will flrst start with the (10;18) MCT
constructedusingthetechniquefromsection3.3. WehaveV = f1;u;v;w;x1;x2;x3;y1;y2;y3g
and T had the following triples:
20
Type 0 f1u;sg, f1;u;wg, f1;s;wg, f1;x1;y1g, f1;x2;y2g, and f1;x3;y3g;
Type 1 fx1;y1;sg, fx2;y2;wg, and fx3;y3;ug;
Type 2 fu;y1;y2g, fy3;s;y2g, and fy3;y1;wg;
Type 3 fx1;x2;y3g, fx1;x2;ug, fx2;x3;y1g, fx2;x3;sg, fx1;x3;y2g and
fx1;x3;wg
So initially we have b = 18. We start by removing fx1;y1;sg and replacing it with
f1;x1;sg and f1;y1;sg. Next we set i = 2 and remove fx2;y2;wg and replacing it with
f1;x2;wg and f1;y2;wg. Now we set i = 3 and remove fx3;y3;ug and replacing it with
f1;x3;ug and f1;y3;ug. After removing all the Type 1 triples we now have b = 21.
We will need to remove all the Type 2 triples. After removing them we replace
them with the triples f1;u;y1g, f1;u;y2g, f1;y1;y2g, f1;y3;sg, f1;y3;y2g, f1;s;y2g,
f1;y3;y1g, f1;y3;wg, and f1;y1;wg. At this point we now have b = 27 this means that
b0 = 3.
Soproceedingasdirectedwenowremovefx1;x2;y3gandreplaceitwithf1;y3;x1gand
f1;y3;x2g making b = 28. Finally we remove fx1;x2;ug and replace it with f1;x1;x2g,
f1;x1;ug and f1;x2;ug giving us a (10;30) MCT.
4.4 v ? 5 mod 6
We will handle all possibilities for v ? 11, the case when v = 5 will be handled in
section B.1. Assume that v = 6n + 5; the minimum value is obtained using Construction
3.2 and will be used as a starting point to obtain the remaining values needed. As done
21
previously we will build a MCT with the desired value for b by carefully replacing select
triples with multiple replacement triples.
We start by choosing any point of V nfa;c;d;e;fg and renaming it 1. Noting that
we start with 6n2 +9n+4 triples, we then categorize the triples in the following manner:
Type 0 All triples of T of the form f1;u;wg where u;w 2 V ?f1g,
Type 1 The triples fa;f;cg, fa;f;dg and fa;f;eg,
Type 2 All triples of T of the form fx;y;ug where x;y 2 V ?fa;b;1g and u 2 V ?f1g.
It follows that we have 3n + 2 Type 0 triples and 3 Type 1 triples. Thus it leaves us
6n2 + 6n ? 1 Type 2 triples. We now proceed to show how to use this to obtain a (v;b)
MCT when 6n2 +9n+4 < b < 18n2 +21n+5.
If b ? 18n2 + 21n + 3 we choose bb?(6n2+9n+4)2 c Type 2 triples. For each such triple
fu;s;wg we remove it and replace it with the triples f1;u;sg, f1;u;wg and f1;s;wg.
Our MCT now has either b or b ? 1 triples, so either we are done or we remove fa;f;cg
and replace it with f1;a;cg and f1;f;cg. If b = 18n2 + 21n + 4 we replace all the Type
2 triples as above, and then remove fa;f;cg and fa;f;dg and replace them with f1;a;cg,
f1;f;cg, f1;a;dg and f1;f;dg.
Example 4.4 (v = 11;b = 25)
Suppose we wish to construct a (11;25) MCT. We will start with the (11;18) MCT we
get from the construction in section 3.2. We have V = fa;c;d;e;f;6;7;8;9;10;1g and T
is made up of:
Type 0 f1;a;10g, f1;f;7g, f1;c;6g, f1;d;8g, and f1;e;9g;
22
Type 1 fa;f;cg, fa;f;dg, and fa;f;eg;
Type 2 fa;6;7g, fa;8;9g, ff;6;9g, ff;8;10g, fc;7;8g, fc;9;10g, fd;6;10g, fd;7;9g, fe;6;8g,
and fe;7;10g.
We flrst need to remove three Type 2 triples, so lets remove fa;6;7g, fa;8;9g, and
ff;6;9g. We then replace them with f1;a;6g, f1;a;7g, f1;6;7g, f1;a;8g, f1;a;9g,
f1;8;9g, f1;f;6g, f1;f;9g, and f1;6;9g. This leaves us with b = 24 so we remove
fa;f;cg and replace it with f1;a;cg and f1;f;cg. This gives us a (11;25) MCT.
23
Chapter 5
Imbrical Design Flaws
When I started this project I initially did what I thought was an exhaustive search for
papers on the subject. After I had a large portion of the results worked out, my advisor
contacted Charles J. Colburn in order to make sure that we had not missed any papers that
may have been out there. It was then that he brought the paper on imbrical designs to our
attention [2]. At that point Dr. Hofiman suggested that I compare my results to those in
[2]
The authors deflne imbrical designs as follows:
\A pair (V;D) is an ID(v;k;?;b) if
(a) jVj = v;
(b) D is a collection of b k{subsets of V called blocks;
(c) every pair of elements of V is in at least ? blocks of D;
(d) for every b 2 D there is a pair fx;yg ? b so that xy is in exactly ? blocks
(fx,yg ia called essential for b);
(d?) equivalently, if D0 ? D, (V;D0) is not an imbrical design."
If k = 3 and ? = 1 the associated imbrical design is a minimal cover by triples. What
they refer to as an essential edge is then what I have referred to as a unique edge. They
also deflne the spectrum as follows:
\Given v, k and ? the spectrum Spec(v;k;?) = fb : there exists ID(v;k;?;b)."
Later, they make the claim that
24
\The results are that min Spec(v;3;1) = ?v3 ?v?12 currency1currency1, max Spec(v;3;1) = ?v?22 ? and
that Specv;3;1 is an interval except that v = 3, b = 2 and v = 7 and b = 8 do not exist."
Their claim that the spectrum is an interval for most values of v is what flrst caught
my attention as it is contradicted by theorem 2.1 of my work. The rest of this chapter
explains why my results don?t agree with theirs.
5.1 The basic augmentation procedure
The authors of [2] make use of what they call augmentations. The augmentations are
very similar to the techniques I used. They both involve the removal of one block followed
by then replacing it with at most 3 new blocks. The main difierence is in [2] they try to
have one generalized process that works in all cases while I used difierent processes tailored
to various situations.
There are two problems with their basic augmentation. The flrst problem involves
being a little to liberal with the term without loss of generality. The authors write:
\Let (V;B) be an ID(v;k;l;b). Let 1 = f10;11;:::;1k?1g 2 B be flxed. Let a be
a block of B, a = fa0;a1;:::;ak?1g, with fa0;ak?1g essential (i.e. in no other block). Thus
not both a0;ak?1 2 1. Assume without loss of generality that if one of them is in 1 it is
a0 and a0 = 1k?1."
That last assumption garners no loss of generality if the augmentation is to be used a
single time, but unfortunately the authors make use of multiple iterations of the augmenta-
tion. Since these are done with 1 flxed, once the flrst augmentation is done its labels are
flxed and any further augmentations are in danger of loss of generality.
25
The more severe of the two problems is the authors have not taken pains to ensure that
there augmentation produces a cover that is still minimal. The steps the authors give us to
take in the augmentation procedure are as follows:
\ 1. Delete from B the block fa0;:::ak?1g.
2. Add to B the block f1i;a0;a1;:::ak?2g where 1i has the least i such that
1i 21?a, provided there is an essential edge in this new block.
3. Add to B the block f1i;a1;a2;:::ak?1g where 1i has the least i such that
1i 21?a, provided there is an essential edge in this new block.
4. Add the block f10;11;:::1k?3;a0;ak?1g. "
Here is an example of the augmentation procedure going wrong. Let V = f1;2;:::;8g
and let B = ff8;1;2g;f8;1;4g;f8;2;4gf8;3;5g;f8;6;7g;f2;3;5g;f3;4;6g;f5;6;1g;
f6;7;2g;f7;1;3g;f8;4;5g;f8;4;7g;f8;5;7gg. If we choose to let 1 = f8;7;6g and a =
f6;4;3g. Following the steps for the augmentation we flrst removef6;4;3g from B. Next we
addf8;6;4gsincef4;6gisessential. Nowwehaveaproblemthoughbecausef8;7;6g;f6;7;2g
;f8;4;7g and f8;6;4g are all in B hence 1 no longer has an essential edge. Since no blocks
will be removed during the rest of the augmentation process we will be left with a cover
that is no longer minimal.
26
5.2 The Proof of the Main Theorem
Even if we found a way to tweak the augmentation so it would still work, there is a
major  aw in the use of the second theorem of the paper to prove the authors claims about
the spectrum of imbrical designs. They state:
\Let k = 3. Suppose that we have a block fa;b;cg all distinct from 10 with ab
repeated, and ac and bc both essential. Then the augmentation to 1ac, 1bc increases the
size by one, and no other augmentation by 1 afiects this."
Thelibertytakenwithnotationinthispassagecausetheauthorsclaimtobeimprecisely
stated. In addition to that the authors provide no proof whatsoever of this claim. If one
carefully considers their implication one can see that augmenting flrst by all blocks sharing
fa;bg with fa;b;cg will leave fa;b;cg with all its edges being essential. At this point,
augmenting by 1 on fa;b;cg will add the blocks f10;a;bg;f10;a;cg and f10;b;cg. So it
no longer adds only one to the size.
A speciflc example of this happening can be obtained taking V and B to be as in
the previous section and letting 1 = f6;7;8g and fa;b;cg = f3;5;2g. In this case f3;5g
is shared with the block f3;5;8g. If we flrst augment by 1 on f3;5;8g we will remove
f3;5;8g and add f3;6;8g If we now augment by 1 on f3;5;2g we will remove f3;5;2g and
add f6;3;5g, f6;5;2g and f6;3;2g.
So we see that the claim the authors make which is the key statement in proving their
claims of the spectrum when k = 3 is quite false. This coupled with the inherent prob-
lems with the augmentation process itself discussed in the previous section unfortunately
invalidates their results.
27
Bibliography
[1] C.C.Lindner and C.A.Rodger, \Design Theory," CRC press LLC, 1997.
[2] E.Mendelsohn and A.Assaf, On the Spectrum of Imbrical Designs, Annals of Discrete
Mathematics 34 (1987), 363{369
[3] Jean Doyen and Richard M. Wilson, Embeddings of Steiner triple systems, Discrete
Math, 5 (1973), 229{239.
28
Appendices
29
Appendix A
Some Specific MCT?s
A.1 (9;13) MCT
V = fd;e;f;1;2;3;4;5;6g, T = ffd;e;1g;fd;e;2g;fe;f;3g;fe;f;4g;fd;f;5g;fd;f;6g;
fd;3;4g;fe;5;6g;ff;1;2g;f1;3;5g;f1;4;6g;f2;3;6g;f2;4;5gg:
A.2 (13;27) MCT
V = fd;e;f;1;2;3;4;5;6;7;8;9;10g, T = ffd;e;1g;fd;e;2g;fe;f;3g;fe;f;4g;fd;f;5g;
fd;f;6g;fd;3;4g;fe;5;6g;ff;1;2g;fd;7;8g;fd;9;10g;fe;7;9g;fe;8;10g;ff;7;10g;
ff;8;9g;f1;3;7g;f1;4;8g;f1;5;9g;f1;6;10g;f2;3;10g;f2;4;9g;f2;5;7g;f2;6;8g;f3;5;8g;
f3;6;9g;f4;5;10g;f4;6;7gg:
A.3 (15;36) MCT
V = fd;e;f;1;2;3;4;5;6;7;8;9;10;11;12g,T = ffd;e;1g;fd;e;2g;fe;f;3g;fe;f;4g;fd;f;5g;
fd;f;6g;fd;3;4g;fe;5;6g;ff;1;2g;fd;7;10g;fd;8;12g;fd;9;11g;fe;7;11g;fe;8;10g;
fe;9;12g;ff;7;12g;ff;8;11g;ff;9;10g;f1;3;10g;f1;4;9g;f1;5;12g;f1;6;11g;f1;7;8g;
f2;3;12g;f2;4;7g;f2;5;8g;f2;6;9g;f2;10;11g;f3;5;11g;f3;6;7g;f3;8;9g;f4;5;10g;
f4;6;8g;f4;11;12g;f5;7;9g;f6;10;12gg:
30
Appendix B
v = 5;7 or 8
B.1 v = 5
V = fa;c;d;e;fg
b = 4 : T = ffa;f;cg;fa;f;dg;fa;f;eg;fc;d;egg
b = 5 : T = ffa;f;cg;ff;c;dg;fc;d;eg;fd;e;ag;fe;a;fgg
b = 6 : T = ffa;f;cg;fa;f;dg;fa;f;eg;fa;c;dg;fa;c;eg;fa;d;egg
B.2 v = 7
V = f1;2;3;4;5;6;7g
b = 7 : T = ff1;2;4g;f1;3;7g;f1;5;6g;f2;3;5g;f2;6;7g;f3;4;6g;f4;5;7gg
b = 9 : T = ff1;2;4g;f1;3;7g;f1;5;6g;f1;2;3g;f1;2;5g;f1;3;5g;f2;6;7g;f3;4;6g;f4;5;7gg
b = 10 : T = ff1;2;5g;f1;3;6g;f1;4;7g;f2;3;5g;f2;3;6g;f2;4;5g;f2;4;7g;f3;4;6g;f3;4;7g;
f5;6;7gg
b = 11 : T = ff1;2;4g;f1;3;7g;f1;5;6g;f1;2;3g;f1;2;5g;f1;3;5g;f1;2;6g;f1;2;7g;f1;6;7g;
f3;4;6g;f4;5;7gg
b = 12 : T = ff1;2;3g;f1;2;4g;f1;2;5g;f1;2;6g;f1;2;7g;f2;3;5g;f2;4;5g;f2;5;6g;f2;6;7g;
f2;5;7g;f3;4;6g;f3;4;7gg
31
b = 13 : T = ff1;2;4g;f1;3;7g;f1;5;6g;f1;2;3g;f1;2;5g;f1;3;5g;f1;2;6g;f1;2;7g;f1;6;7g;
f1;3;4g;f1;3;6g;f1;4;6g;f4;5;7gg
b = 15 : T = ff1;2;4g;f1;3;7g;f1;5;6g;f1;2;3g;f1;2;5g;f1;3;5g;f1;2;6g;f1;2;7g;f1;6;7g;
f1;3;4g;f1;3;6g;f1;4;6g;f1;4;5g;f1;4;7g;f1;5;7gg
B.3 v = 8
V = f1;1;2;3;4;5;6;7g
b = 11 : T = ff1;1;2g;f1;1;4g;f1;2;4g;f1;3;5g;f1;6;7g;f2;3;5g;f3;4;6g;f4;5;7g;
f5;6;1g;f6;7;2g;f7;1;3gg
b = 12 : T = ff1;1;2g;f1;1;4g;f1;2;4g;f1;3;5g;f1;6;7g;f1;2;3g;f1;2;5g;f3;4;6g;
f4;5;7g;f5;6;1g;f6;7;2g;f7;1;3gg
b = 13 : T = ff1;1;2g;f1;1;4g;f1;2;4g;f1;3;5g;f1;6;7g;f1;3;4g;f1;3;6g;f1;4;6g;
f2;3;5g;f2;6;7g;f4;5;7g;f5;6;1g;f7;1;3gg
b = 14 : T = ff1;1;2g;f1;1;4g;f1;2;4g;f1;3;5g;f1;6;7g;f1;3;4g;f1;3;6g;f1;4;6g;
f1;2;3g;f1;2;5g;f2;6;7g;f4;5;7g;f5;6;1g;f7;1;3gg
b = 15 : T = ff1;1;2g;f1;1;4g;f1;2;4g;f1;3;5g;f1;6;7g;f1;3;4g;f1;3;6g;f1;4;6g;
f1;2;3g;f1;2;5g;f1;2;6g;f1;2;7g;f4;5;7g;f5;6;1g;f7;1;3gg
b = 16 : T = ff1;1;2g;f1;1;4g;f1;2;4g;f1;3;5g;f1;6;7g;f1;3;4g;f1;3;6g;f1;4;6g;
f1;2;3g;f1;2;5g;f1;5;6g;f1;5;1g;f1;6;1g;f2;6;7g;f4;5;7g;f7;1;3gg
32
b = 17 : T = ff1;1;2g;f1;1;4g;f1;2;4g;f1;3;5g;f1;6;7g;f1;3;4g;f1;3;6g;f1;4;6g;
f1;2;3g;f1;2;5g;f1;5;6g;f1;5;1g;f1;6;1g;f1;2;6g;f1;2;7g;f4;5;7g;
f7;1;3gg
b = 18 : T = ff1;1;4g;f1;1;5g;f1;1;6g;f1;2;4g;f1;2;5g;f1;2;6g;f1;2;7g;f1;3;4g;
f1;3;5g;f1;3;6g;f1;4;5g;f1;4;6gf1;4;7g;f1;5;6g;f1;5;7g;f1;6;7g;
f1;3;7g;f1;2;3gg
b = 19 : T = ff1;1;2g;f1;1;4g;f1;1;5g;f1;1;6g;f1;2;3g;f1;2;4g;f1;2;5g;f1;2;6g;
f1;2;7g;f1;3;4g;f1;3;5g;f1;3;6g;f1;4;5g;f1;4;6gf1;4;7g;f1;5;6g;
f1;5;7g;f1;6;7g;f1;3;7gg
b = 21 : T = ff1;1;2g;f1;1;3g;f1;1;4g;f1;1;5g;f1;1;6g;f1;1;7g;f1;2;3g;f1;2;4g;
f1;2;5g;f1;2;6g;f1;2;7g;f1;3;4g;f1;3;5g;f1;3;6g;f1;3;7g;f1;4;5g;
f1;4;6gf1;4;7g;f1;5;6g;f1;5;7g;f1;6;7gg
33