Triple Systems

by Colbourn, Charles J.; Rosa, Alex

• ISBN13: 9780198535768
• ISBN10: 0198535767
• Format: Hardcover
• Copyright: 1999-07-29
• Publisher: Clarendon Press

Summary

Triple systems are among the simplest combinatorial designs, and are a natural generalization of graphs. They have connections with geometry, algebra, group theory, finite fields, and cyclotomy; they have applications in coding theory, cryptography, computer science, and statistics. Triplesystems provide in many cases the prototype for deep results in combinatorial design theory; this design theory is permeated by problems that were first understood in the context of triple systems and then generalized. Such a rich set of connections has made the study of triple systems anextensive, but sometimes disjointed, field of combinatorics. This book attempts to survey current knowledge on the subject, to gather together common themes, and to provide an accurate portrait of the huge variety of problems and results. Representative samples of the major syles of proof techniqueare included, as is a comprehensive bibliography.

Table of Contents

An historical introduction	1	(12)
Beginnings	1	(1)
Kirkman's ``On a problem in combinations''	2	(4)
Kirkman's ``On the puzzle of the fifteen young ladies''	6	(2)
Netto, Moore, and Heffter	8	(2)
Cole, Cummings, and White	10	(1)
Fisher, Yates, and Bose	11	(2)
Design-theoretic fundamentals	13	(10)
Designs	13	(2)
Balanced incomplete block designs	13	(1)
Pairwise balanced designs	14	(1)
Group divisible designs	14	(1)
Transversal designs and orthogonal arrays	14	(1)
Latin squares and quasigroups	15	(2)
Factorizations and graph decompositions	17	(6)
Edge-colourings	18	(1)
1-factorizations	19	(1)
Regular factors	20	(1)
2-factorizations	21	(1)
Absence of factors	21	(1)
Room squares	21	(2)
Existence: direct methods	23	(16)
Constructions from latin squares	24	(4)
Equivalence with Steiner quasigroups	24	(1)
Bose's construction and variants	25	(2)
Idempotent latin squares	27	(1)
A complete existence proof for triple systems	27	(1)
Primes and prime powers	28	(1)
Projective and affine spaces	29	(1)
Peltsohn's construction	30	(2)
Constructions from integer sequences	32	(2)
The Schreiber-Wilson construction	34	(1)
Computational methods	35	(4)
Backtracking	36	(1)
Hillclimbing	37	(2)
Existence: recursive methods	39	(10)
Direct and indirect products	39	(1)
Doubling constructions	40	(3)
The 2v -- 2 and 3v -- 4 constructions	43	(1)
PBDs, GDDs, and PBD-closure	44	(2)
Fundamental construction of Wilson	46	(3)
An application to GDDs	46	(3)
Isomorphism and invariants	49	(12)
The computational complexity of isomorphism	49	(3)
Isomorphism algorithms for fixed index	52	(5)
Steiner triple systems: Miller's algorithm	52	(3)
Automorphisms	55	(1)
Fixed index: Babai-Luks algorithm	55	(2)
Isomorphism invariants	57	(3)
Trains and compact trains	57	(1)
Fragments and cycle structure	58	(1)
Neighbourhood graphs	59	(1)
Intersections and clique analysis	59	(1)
Work points	60	(1)
Enumeration	61	(16)
Small orders	61	(9)
Asymptotics	70	(2)
Computational lower bounds	72	(2)
Work points	74	(3)
Subsystems and holes	77	(24)
One subsystem or hole	77	(5)
Group divisible designs	82	(2)
Simple triple systems	84	(1)
Subsystems of simple systems	85	(2)
Relatives of 3-GDDs	87	(4)
Modified 3-GDDs	87	(1)
Uniform holey 3-GDDs	88	(1)
Holey 3-GDDs	89	(1)
Incomplete 3-GDDs	89	(2)
3-GDDs with first and second associates	91	(6)
Two groups	93	(1)
Group size two	94	(2)
The general problem	96	(1)
GDDs and constant weight codes	97	(1)
Dimension	98	(2)
Work points	100	(1)
Automorphisms I: small groups	101	(40)
Orbits and orbit representatives	101	(1)
Cyclic automorphisms	101	(14)
Direct constructions	102	(4)
Recursive constructions	106	(1)
Cyclic systems with cyclic subsystems	107	(2)
Multipliers and multiplier automorphisms	109	(1)
Triple systems with multiplier automorphisms	110	(4)
Enumerative results	114	(1)
Rotational automorphisms	115	(19)
Reverse triple systems	115	(2)
1-rotational systems	117	(4)
k-rotational systems	121	(2)
Existence for composite orders	123	(3)
Recursive constructions for rotational STSs	126	(3)
Existence for large prime orders	129	(5)
Which permutations are automorphisms?	134	(4)
Fixed points	134	(1)
Involutions	135	(1)
3-cycles	136	(1)
Bicyclic automorphisms	136	(1)
Transrotational automorphisms	137	(1)
Other automorphisms	137	(1)
An application: halving triple systems	137	(1)
Automorphism-free triple systems	138	(2)
Work points	140	(1)
Automorphisms II: large groups	141	(14)
Group actions	141	(1)
Implications from group theory	142	(2)
2-transitive STSs	144	(1)
2-homogeneous STSs	144	(1)
Block-transitive STSs	145	(2)
Veblen points and quadrilaterals	147	(1)
Hall triple systems	148	(3)
Abstract groups	151	(2)
Graphical triple systems	153	(1)
Work points	154	(1)
Leaves and partial triple systems	155	(22)
Necessary conditions	155	(2)
Recognizing &lamda;-leaves	157	(2)
Maximal partial triple systems	159	(5)
Maximum partial triple systems	159	(2)
Minimum maximal partial triple systems	161	(2)
The spectrum of maximal partial triple systems	163	(1)
Equitable partial triple systems	164	(1)
Quadratic leaves	165	(1)
Subgraphs of leaves	166	(1)
An application to group testing	166	(8)
The structure of pairs in an HS-family	68	(101)
Maximum WR-families	169	(4)
Testing each item at most three times	173	(1)
Rodl's nibble method	174	(2)
Work points	176	(1)
Excesses and coverings	177	(8)
Necessary conditions	177	(1)
Minimum excesses	178	(2)
The spectrum for minimal coverings	180	(2)
Quadratic excesses	182	(1)
Excesses and leaves: nuclear designs	183	(1)
Work points	184	(1)
Embedding and its variants	185	(14)
Embedding	185	(9)
Finite embedding theorems	185	(2)
A lower bound	187	(2)
Linear embeddings for index one	189	(1)
Linear embeddings for all indices	189	(4)
Simple embeddings	193	(1)
Enclosing	194	(2)
Immersion and intricacy	196	(1)
Work points	197	(2)
Neighbourhoods	199	(10)
Graphs as neigbourhoods	199	(1)
Index two	200	(2)
Index three	202	(1)
Simple neighbourhoods	203	(2)
Neighbourhood uniform triple systems	205	(1)
Double neighbourhoods for index one	206	(1)
Uniform and perfect triple systems	206	(2)
Work points	208	(1)
Configurations	209	(38)
Constant and variable configurations	209	(4)
Avoidance: Pasch configurations	213	(12)
Stinson and Wei's construction	217	(1)
Bose-type constructions	218	(2)
Lu's construction	220	(1)
GDD constructions	221	(1)
The current status	222	(2)
Erasure codes	224	(1)
Avoidance of mitres	225	(2)
5-sparse STSs	226	(1)
Avoidance: weakly union-free systems	227	(9)
Direct constructions	228	(4)
Recursive constructions	232	(2)
Group testing revisited	234	(2)
Avoidance in general	236	(2)
Block intersection graphs	238	(2)
Decompositions	240	(6)
Four-line configurations	242	(1)
Simultaneous decompositions	243	(2)
Ubiquity	245	(1)
Work points	246	(1)
Intersections	247	(20)
Making two STSs disjoint	247	(1)
Intersections of STSs	248	(2)
Intersections of 3-GDDs	250	(1)
Orthogonal Steiner triple systems	251	(10)
Constructions and uses of OGDDs	253	(4)
OSTSs with v υ ≡ 1 (mod 6)	257	(2)
OSTSs with v υ ≡ 3 (mod 6)	259	(2)
More OGDDs	261	(4)
Intersections of resolvable STSs	265	(1)
Work points	266	(1)
Large sets and partitions	267	(12)
Large sets: even index	269	(1)
Large sets: index three	269	(1)
Large sets: index one	269	(5)
Large sets of 3-GDDs	274	(2)
Threshold schemes	275	(1)
Mutually almost disjoint systems	276	(1)
Large sets of Kirkman triple systems	277	(1)
Overlarge sets	278	(1)
Work points	278	(1)
Support sizes	279	(25)
Trades: the linear algebra of designs	279	(4)
Support sizes: necessity	283	(3)
Support sizes: sufficiency	286	(15)
Small orders	286	(1)
Intersections and support	287	(1)
Recursive constructions wit fixed index	288	(3)
Partitions with subsystems	291	(9)
Putting the pieces together	300	(1)
Fine structure	301	(1)
Defining sets	302	(1)
Work points	303	(1)
Independent sets	304	(21)
The independence number	304	(1)
Complete arcs, spanning and scattering sets	305	(10)
Partitions into complete arcs	315	(1)
Generating sets	316	(3)
Covering sets	319	(1)
An application: point codes	320	(4)
Work points	324	(1)
Chromatic number	325	(19)
Colourings	325	(5)
Equitable weak colourings	330	(2)
Equitable colourings with many colours	332	(6)
Balanced colourings	338	(1)
Strong colouring	339	(1)
Strict colourings and the upper chromatic number	340	(1)
Achromatic number	341	(1)
The complexity of strong and weak colouring	342	(1)
Work points	343	(1)
Chromatic index and resolvability	344	(29)
Partial parallel classes	344	(1)
Resolvable triple systems	345	(3)
Kirkman frames and resolvable 3-GDDs	348	(10)
Frames	348	(2)
Reverse frames and an application	350	(1)
Nearly Kirkman triple systems	351	(1)
Resolvable 3-GDDs	352	(2)
Kirkman school project designs	354	(2)
Semiframes	356	(1)
Resolvable coverings	357	(1)
{2, 3}-PBDs	357	(1)
Colouring triples and the chromatic index	358	(9)
Hanani triple systems	358	(1)
Orthogonal double covers	359	(1)
Rosa triple systems	359	(6)
Minimum chromatic index	365	(1)
Upper bound	366	(1)
Computational complexity	367	(3)
The complexity of block-colouring	367	(1)
Generating Kirkman triple systems quickly	367	(3)
Enumeration of Kirkman triple systems	370	(1)
Kirkman triple systems with subsystems	370	(2)
Work points	372	(1)
Orthogonal resolutions	373	(8)
Introduction	373	(1)
Generalized Room squares of degree 3	374	(1)
Kirkman squares	375	(2)
Kirkman cubes	377	(1)
Doubly resolvable twofold triple systems	378	(1)
Room rectangles and parallelepipeds	378	(2)
Work points	380	(1)
STSs with two subsystems	381	(18)
Necessary conditions for -ISTSs	382	(1)
Metting the bound	383	(2)
Near the minimum	385	(11)
Lattice ISTSs	386	(1)
Intersecting cases	387	(2)
Disjoint cases	389	(1)
Eframes	390	(4)
Incomplete group divisible designs	394	(2)
Consequences	396	(2)
Work points	398	(1)
Nested and derived triple systems	399	(11)
Nested triple systems	399	(5)
Index one	400	(3)
Higher indices	403	(1)
Nesting GDDs and partial triple systems	403	(1)
Nesting into larger blocks	404	(1)
Compatible Steiner triple systems	404	(2)
Perpendicular arrays of triple systems	406	(1)
Derived triple systems	407	(2)
Heterogeneity and homogeneity	408	(1)
Work points	409	(1)
Decomposability	410	(12)
Existence	410	(4)
The complexity of decomposition	414	(2)
A finite basis theorem	416	(1)
Partitions into indecomposable systems	416	(2)
Separations of triple systems	418	(1)
Work points	419	(3)
Directed triple systems	422	(20)
Existence I: basic constructions	422	(2)
Existence II: directing with conflict resolution	424	(2)
Existence III: the eulerian algorithm	426	(3)
Consequences of directability	429	(1)
Automorphisms	430	(2)
The number of directed triple systems	432	(2)
Intersections and large sets	434	(7)
Work points	441	(1)
Mendelsohn triple systems	442	(15)
Existence: recursions and PBD constructions	442	(2)
Orienting a triple system	444	(1)
The number of Mendelsohn triple systems	445	(2)
Cyclic and rotational MTSs	447	(1)
Subsystems, intersection, and large sets	448	(3)
Embedding partial MTSs	451	(1)
Resolvable and almost resolvable MTSs	452	(2)
Hybrid triple systems	454	(2)
Work points	456	(1)
Bibliography	457	(94)
Index	551