Census of 3-(12,6,4) and 2-(11,5,4) Designs

The research is grounded in combinatorial theory, specifically addressing the challenge of constructing and enumerating non-isomorphic block designs. The introduction clearly states the aim: to generate all possible non-isomorphic 3-(12,6,4) and 2-(11,5,4) designs. This involves understanding the properties of block designs, which are characterized by a fixed number of blocks of size k, chosen from v distinct points or symbols, such that the structure exhibits a degree of balance in the occurrences of singletons, pairs, triples, etc. The existence of designs with given parameters is not guaranteed, and even when they exist, finding all non-isomorphic structures presents a significant combinatorial problem. The thesis directly tackles this problem, focusing on the creation and classification of these specific designs.

A crucial aspect of the methodology is the extensive use of computer-assisted techniques. The researchers balanced structures to produce a pool of 3-designs, from which isomorphic copies were then systematically removed. This process of sieving isomorphs is essential to ensure that only unique designs are retained. The use of a computer program is highlighted as necessary to manage the computational complexity of the problem. The process involved constructing designs, identifying their automorphisms, and utilizing point orbits to efficiently access the embedded 2-(11,5,4) designs. The procedure was repeated using the other block type as a starting point, further enhancing the completeness of the search. The final results of these procedures are referenced as being in Part II, Sections II and III, indicating a significant volume of generated data.

The core methodology focuses on achieving balance within the designs. Two distinct methods for balancing are described. One method partitions pairs and tests alignments to ensure the correct occurrence of triples. The other method focuses on independent positioning of points to balance triples, facilitated by the absence of certain triple combinations. The second method is highlighted as more efficient but still tedious when done manually. Consequently, a computer program was developed to automate this process. The structure of this program (MAIN subroutine and IWORK and IFIT subroutines) is described briefly, showcasing the program's role in systematically generating and testing possible designs. The input and output of the program, such as the use of arrays to store and manage design data, are mentioned, highlighting the intricacies of the computational approach.

A significant portion of the research is dedicated to ensuring the elimination of isomorphic designs. The methods used exploit symmetries and permutations to identify and remove duplicates. The absence of permutations interchanging specific point sets is noted as influencing the expectation of isomorphic pairs. The commutativity of a table relating pair types is used as a check for symmetry. A computer program is employed to list 3-designs and their embedded 2-(11,5,4) designs, aiding in sorting and identifying transitivity sets. The efficiency of the isomorphism elimination process is a recurring theme, with techniques mentioned to reduce computational effort by focusing on non-equivalent ways to select triples. Further checks are mentioned, such as utilizing permutations to fix quadruples and comparing index values to detect isomorphic structures, demonstrating a careful approach to ensuring the accuracy of the results.

The construction of 3-(12,6,4) designs initially focused on avoiding repeated blocks. A computational approach was employed to create and then filter these designs, eliminating isomorphic copies. The process involved generating structures, balancing them for the remaining points, and then sieving out the isomorphs to arrive at a set of unique designs. The use of automorphisms and point orbits to facilitate the identification of isomorphic structures and the related 2-(11,5,4) designs is highlighted. This initial phase emphasizes the computational power needed to address the combinatorial challenges of generating and then analyzing these complex structures. The iterative nature of the process, repeating with blocks of a different type, further increased the thoroughness of the search for all non-isomorphic solutions.

A key method involved starting with a skeleton structure and systematically completing it. Two approaches were outlined for this completion process. The first involved partitioning pairs and testing various alignments to ensure a balanced distribution of triples, using the property of self-complementarity to streamline the process. The second method involved independent positionings of points to balance (0,*,•) triples, aided by the absence of (0,•,f) triples. This resulted in a more efficient, though still manually tedious, approach for design completion. The inherent complexity and potential for human error led to the development of a computer program to automate this completion and balancing process for constructing the 3-(12,6,4) designs, making the method more robust and repeatable.

The description delves into the structure and functionality of the developed computer program. The program comprises a main section (MAIN) and two associated subroutines: IWORK and IFIT. MAIN's role is to systematically generate possible designs, utilizing IWORK to develop all possibilities with a fixed block. The output is a 2 x 15 array representing the design in abbreviated form. IFIT is described as handling a crucial step in the algorithm (Step 5), searching for compatible positions for points, based on input data and controlling conditions. The extensive branching in Step 5, visualized by a flow chart, highlights the combinatorial nature of the problem and underscores the necessity of efficient algorithmic design for tackling the computational task. Data mapping techniques are also referenced to help manage the program's input data requirements.

The discussion emphasizes the importance of efficient isomorphism elimination to manage the sheer number of generated configurations. Specific strategies are discussed to minimize computational effort. The use of permutations that fix certain quadruples or point sets is highlighted as crucial for reducing the number of possibilities. Manual calculations are mentioned for reducing the non-equivalent ways to select initial pairs. The algorithm ensures a standard selection of representative pairings from equivalence classes, aiding in comparison and elimination of duplicates. Permutation adjustments to the index values are described as a means of testing pairings under specific permutations and eliminating those resulting in repeated quadruples. This detailed explanation of the computational techniques underlines the necessity of advanced algorithms and efficient data handling for successful construction and analysis of these designs.

The analysis section begins by presenting the results of the 3-(12,6,4) design generation process. A total of 426 non-isomorphic designs were identified, a key finding of the research. These designs were generated under the constraint of no repeated blocks. The methodology involved using automorphisms of the designs to determine point orbits, which in turn provided access to the embedded 2-(11,5,4) designs. The non-self-complementary nature of the 2-(11,5,4) designs is mentioned as influencing the analysis and classification process. The relationship between the 3-(12,6,4) and 2-(11,5,4) designs is highlighted, emphasizing the point restrictions used to derive the 2-(11,5,4) designs from the larger 3-(12,6,4) structures. This close connection underscores the importance of understanding both design types in the context of this research.

The analysis section details the derivation of the 2-(11,5,4) designs from the 3-(12,6,4) designs. A significant result is the identification of 3737 non-isomorphic 2-(11,5,4) designs derived through point restrictions from the 426 non-isomorphic 3-(12,6,4) designs. The use of smaller designs (2-(11,5,4)) as a means of processing and sorting the larger 3-(12,6,4) designs is described as advantageous. This approach facilitated the determination of transitivity sets within the 3-designs. A computer program played a central role in this process, providing listings of both the 3-designs and their embedded 2-(11,5,4) designs. This integrated approach showcases the researchers' effective use of computational tools in managing and analyzing a large volume of generated designs within the context of combinatorial theory.

The analysis involved a detailed classification of the designs. The 426 non-isomorphic 3-(12,6,4) designs were categorized according to the number of AC and B type blocks they contained. The categorization also considers the presence of reducible designs. The relatively low proportion of reducible designs compared to non-reducible designs is highlighted as an important observation. This systematic categorization provides insights into the characteristics and distribution of the generated designs. The information obtained helps in understanding the overall structure and properties of the generated 3-(12,6,4) and 2-(11,5,4) designs within the field of combinatorial design theory. The resulting data likely contributed to conclusions on the exhaustive nature of the construction methods.

This section addresses the enumeration of block designs allowing repeated blocks, a problem distinct from the previous focus on designs without repeated blocks. The researchers acknowledge that the previous methods are not directly applicable and that new techniques are necessary. The text suggests that some insight might be gained from earlier work on reducible designs with repeated blocks, indicating a potential link between approaches. The high degree of regularity in the skeleton structure is highlighted as a factor that may increase the number of isomorphic designs produced, necessitating strategies for early elimination of equivalents to reduce computational burden. This section marks a shift in the research's focus and methodology, necessitating the development of new algorithms and strategies specifically designed for the case of repeated blocks.

The core of this section involves the generation and analysis of 2-(11,5,4) designs with repeated blocks. A Prime 750 computer was used in conjunction with a purpose-built program to create these designs. Due to the unexpected large number of designs generated, the researchers implemented a strategy of immediately eliminating isomorphs to minimize storage needs. While a computer program was used for efficient isomorphism elimination, some more difficult cases required manual verification. The computational effort involved is described as moderate, indicating that the problem, even with the use of a computer, was not trivial. The approach for handling these designs showcases how computational and manual methods can be combined for effective analysis in complex combinatorial problems.

The 656 non-isomorphic 2-(11,5,4) designs with repeated blocks were used to construct 3-(12,6,4) designs. This involved extending the 2-designs through complementation and then sieving isomorphs from the resulting pool of 3-designs. This process yielded 119 non-isomorphic 3-(12,6,4) designs that contain the 656 2-designs as point restrictions. The determination of automorphism groups and point orbits confirmed that these 119 designs exactly contained the 656 2-designs. The occurrence of the 37 reducible 2-(11,5,4) designs within this set is presented as evidence that the construction technique is exhaustive. The final count of 4393 non-isomorphic 2-(11,5,4) designs is stated (3509 + 228 + 656), providing a comprehensive census for this class of designs.

The final section summarizes the findings related to block designs allowing repeated blocks. The research resulted in the identification of 656 non-isomorphic 2-(11,5,4) designs containing repeated blocks. These designs were categorized based on the number of blocks of each type they contain. The researchers used a computer program to generate and analyze these designs, employing strategies for minimizing storage requirements by immediately eliminating isomorphs after each case was completed. Although a computer program handled most of the isomorphism elimination, the more complex instances required manual examination. The computational time required was moderate, reflecting the significant computational burden involved in this aspect of the study. The total number of non-isomorphic 2-(11,5,4) designs, including those with and without repeated blocks, is given as 4393 (3509 + 228 + 656), demonstrating a comprehensive enumeration of this design type.

The 656 non-isomorphic 2-(11,5,4) designs with repeated blocks were integrated into the overall census of 3-(12,6,4) designs. This integration involved extending the 2-designs via complementation and systematically removing isomorphs to generate 3-(12,6,4) designs. This process resulted in 119 non-isomorphic 3-(12,6,4) designs, which, upon further analysis of their automorphism groups and point orbits, were confirmed to contain exactly the 656 non-isomorphic 2-(11,5,4) designs. The predicted occurrence of the 37 reducible 2-(11,5,4) designs lends support to the claim that the construction techniques used in this part of the research were exhaustive. This step is crucial to completing the overall census of both design types and highlights the complexity of integrating results from different construction methods.

The conclusion summarizes the complete census of 2-(11,5,4) designs, stating a total of 4393 non-isomorphic designs. The precise number of non-isomorphic 3-(12,6,4) designs is not explicitly stated in the conclusion but is implied to be considerably higher than the 426 designs identified without repeated blocks. The researchers' methods involved both computational and manual techniques, demonstrating how the strengths of each approach can be leveraged in combinatorial problems. The researchers note that a more manual approach might have reduced the overall computer time used. The overall contribution is a comprehensive analysis of both design types with and without repeated blocks, highlighting the challenges and methods employed in the exhaustive enumeration of these intricate combinatorial structures.