Catálogo de publicaciones - libros

Combinatorial design theory (or just design theory) is a branch of discrete mathematics which originated in the design of statistical experiments for agriculture and through generalization of various recreational problems.

This chapter gives a brief introduction to graphs, designs, codes, and concepts related to these. Although classification algorithms for graphs are not considered in this book, graphs provide a convenient framework for several of the concepts and algorithms to be discussed.

A quick browse through the [116] indicates that, perhaps more than any other discipline in contemporary mathematics, combinatorics is characterized by the fact that the objects of interest can be represented in a large number of different but nevertheless equivalent ways. Typically there is no single best representation for a particular object; each representation has its advantages and drawbacks. This is especially true when we are designing a classification algorithm for objects of a given type.

Central to classification is the problem of exhaustively generating, without isomorphs, all objects meeting a collection of constraints. This chapter looks at general techniques for solving such problems. There are two main topics to consider: exhaustive generation and isomorph rejection.

In developing classification algorithms, one recurrently encounters subproblems belonging to a few common problem classes. Algorithms for solving such problems are discussed in this chapter. The reader who is not interested in implementational details of classification algorithms may well skip this chapter and assume that there is a “black box” that takes care of these tasks. Those who wish to implement classification algorithms, however, should notice that these auxiliary algorithms often constitute the core of the whole search and thereby affect the overall efficiency in a direct way. On the other hand, the chapter can also be studied separately to get an insight into some contemporary algorithms for several important hard problems (for which no polynomial time algorithms are known).

In this chapter we turn to the first main topic of this book, classification of designs. The designs to be discussed are divided into three classes: balanced incomplete block designs (BIBDs) – that is, 2-designs – are considered in Sect. 6.1, -designs with ≥ 3 in Sect. 6.2, and resolutions of designs in Sect. 6.3. In the discussion of resolutions of designs, the main focus is on resolutions of BIBDs. Extensive tables of classification results are provided at the end of each section. Finally, in Sect. 6.4, classification of designs with certain additional properties is briefly discussed.

In this chapter, classification of several main classes of codes are considered: unrestricted error-correcting and covering codes in Sects. 7.1 and 7.2, respectively, and error-correcting linear codes in Sect. 7.3. Various subclasses of these codes are also discussed, including equidistant codes and constant weight codes.

In this chapter, we study classification of combinatorial objects that are closely related to codes and designs. The objects considered can if fact in most cases be defined as certain codes or designs; algorithms and ideas from Chaps. 6 and 7 are then directly applicable.

So far we have considered the problem of classifying some general families of combinatorial objects. In practice, however, one is often interested in a subfamily of these with certain additional properties. There are two possibilities for carrying out such a classification, which we have already encountered in discussing classification algorithms for resolutions of designs in Sect. 6.3: either all objects are classified and these are searched for the particular properties, or the additional properties are made inherent in the classification. The former approach can often be implemented easily using existing computer programs, but the latter approach is computationally more efficient.

In the Introduction, problems related to combinatorial objects were divided into those of , and , all of which can be attacked with computational methods. The existence problem – whenever answered in the positive by explicit construction – difiers from the others as the constructed object almost without exception can be presented in the published work and checked by hand calculation or by easy computations. Results related to the other types of problems, however, are of intrinsically different nature, and lead us to the somewhat controversial issue of validity of computational results.