3 - Constructing combinatorial objects via cliques

Summary

Abstract

Many fundamental combinatorial objects, including balanced incomplete block designs and error-correcting codes, can be constructed and classified via cliques in certain problem-specific graphs. Various such objects are here identified and surveyed, and the utilization of clique algorithms in the construction of these is considered. Occasionally the type of problem admits a formulation as an instance of the exact cover problem, which, for computational reasons, is even more desirable.

Introduction

Cliques and independent sets are two of the most fundamental concepts in graph theory. A clique in a graph G = (V, E) is a subset of vertices V′ ⊆ V that induces a complete graph. (A complete graph is a graph where all vertices are mutually adjacent.) An independent set, on the other hand, is a subset of vertices V′ ⊆ V that induces an empty graph. Obviously, a clique in a graph G is an independent set in the complement graph Ḡ, and vice versa, so without loss of generality one may focus on just one of these concepts. Note that cliques are occasionally defined as complete subgraphs rather than sets; we choose the latter alternative, which is much more convenient.

In the current work we study combinatorial objects that can be viewed as set systems (but when discussing these objects later, they will generally not be treated using the set system formulation). A set system is a collection of subsets of a given set X, S = {S₁, S₂, …, S_m}, S_i ⊆ X, which has some additional specific properties.