TCS / Research / Publications / Constructing Certain Combinatorial Structures by Computational Methods

# Constructing Certain Combinatorial Structures by Computational Methods

Reference:

Harri Haanpää. Constructing certain combinatorial structures by computational methods. Research Report A89, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, February 2004. Doctoral dissertation.

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.

Keywords:

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

Suggested BibTeX entry:

@techreport{HUT-TCS-A89,
author = {Harri Haanp{\"a}{\"a}},
institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
month = {February},
note = {Doctoral dissertation},
number = {A89},
pages = {32},
title = {Constructing Certain Combinatorial Structures by Computational Methods},
type = {Research Report},
year = {2004},
}

 NOTE: Papers available through URL below. PostScript (568 kB) GZipped PostScript (267 kB) PDF (272 kB) See lib.hut.fi ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.