Constructing certain combinatorial structures by computational methods
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
32, [68]
Series
Research reports / Helsinki University of Technology, Laboratory for Theoretical Computer Science. A, 89
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.Description
Other note
Parts
- Haanpää H., 2000. A lower bound for a Ramsey number. Congressus Numerantium 144, pages 189-191. [article1.pdf] © 2000 Utilitas Mathematica Publishing Inc. By permission.
- 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. [article2.pdf] © 2003 Elsevier Science. By permission.
- Haanpää H. and Kaski P., The near resolvable 2-(13,4,3) designs and thirteen-player whist tournaments. Designs, Codes and Cryptography, to appear. [article3.pdf] © 2004 by authors and © 2004 Kluwer Academic Publishers. By permission.
- Haanpää H., Huima A. and Östergård P. R. J., Sets in ℤ<sub>n</sub> with distinct sums of pairs. Discrete Applied Mathematics, in press. [article4.pdf] © 2004 by authors and © 2004 Elsevier Science. By permission.
- 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. [article5.pdf] © 2004 by authors.
- Haanpää H., 2004. Minimum sum and difference covers of Abelian groups. Helsinki University of Technology, Laboratory for Theoretical Computer Science, Research Report A88. [article6.pdf] © 2004 by author.