The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Constructing Certain Combinatorial Structures by Computational Methods

Harri Haanpää

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Department of Computer Science and Engineering for public examination and debate in Auditorium T2 at Helsinki University of Technology (Espoo, Finland) on the 27th of February, 2004, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-6942-2)   [288 KB]
Dissertation is also available in print (ISBN 951-22-6941-4)

Abstract

Combinatorics is a branch of mathematics that generally deals with a finite or at most countably infinite set and collections of its subsets. These collections must then satisfy certain criteria depending on the class of objects and the problem being considered.

The most fundamental problem in combinatorics is the problem of existence: Does a combinatorial structure that satisfies the given requirements exist? In general, it is straightforward to verify that a proposed structure satisfies the required criteria, but finding a structure of the required type is difficult. If a structure of the required type exists, any method that constructs one is sufficient to settle the existence question.

Two problems closely related to the existence problem are the enumeration problem – how many different combinatorial structures of the required type exist – and the optimization problem – which combinatorial structure of the required type is the best, judged by some criterion.

A computer may be very useful in solving problems of the three types mentioned above. If it is suspected that a structure of the required kind exists, one may design a computer program to sample the space of possible structures until one that satisfies the criteria is found. To show the nonexistence of a structure, to enumerate the structures of a given kind, or to determine the best structure of a given kind, it is generally necessary to conduct a case-by-case analysis of all possible structures, which is a task for which a computer is especially suited. It is, however, often a nontrivial task to design an efficient algorithm for such an analysis.

In this thesis several ways of applying computational methods to combinatorial problems are described. Tabu search on graphs with cyclic symmetry is used to obtain a lower bound for a Ramsey number, an orderly backtrack search with isomorph rejection is applied to a particular class of codes to classify certain designs and the whist tournaments with up to thirteen players, and another orderly search is used to obtain the optimal sum and difference packings and covers of small Abelian groups.

This thesis consists of an overview and of the following 6 publications:

  1. Haanpää H., 2000. A lower bound for a Ramsey number. Congressus Numerantium 144, pages 189-191. © 2000 Utilitas Mathematica Publishing Inc. By permission.
  2. Haanpää H. and Östergård P. R. J., 2003. Classification of whist tournaments with up to 12 players. Discrete Applied Mathematics 129, No. 2-3, pages 399-407. © 2003 Elsevier Science. By permission.
  3. Haanpää H. and Kaski P., The near resolvable 2-(13,4,3) designs and thirteen-player whist tournaments. Designs, Codes and Cryptography, to appear. © 2004 by authors and © 2004 Kluwer Academic Publishers. By permission.
  4. Haanpää H., Huima A. and Östergård P. R. J., Sets in ℤn with distinct sums of pairs. Discrete Applied Mathematics, in press. © 2004 by authors and © 2004 Elsevier Science. By permission.
  5. Haanpää H. and Östergård P. R. J., 2004. Sets in Abelian groups with distinct sums of pairs. Helsinki University of Technology, Laboratory for Theoretical Computer Science, Research Report A87. © 2004 by authors.
  6. Haanpää H., 2004. Minimum sum and difference covers of Abelian groups. Helsinki University of Technology, Laboratory for Theoretical Computer Science, Research Report A88. © 2004 by author.

Keywords: balanced incomplete block design, difference cover, difference packing, isomorph rejection, orderly algorithm, Ramsey number, Sidon set, sum cover, sum packing, whist tournament

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2004 Helsinki University of Technology

Last update 2011-05-26