Randomized approaches to combinatorial packing and covering problems

Many important questions can be formulated as covering and packing problems. This makes the study of such problems crucial both from an algorithmic and a more structural point of view. Recent ideas and methods from discrete probability theory have led to several breakthroughs in the area, with the potential to reshape the field.

Here in a packing problem the task is to organize as many elements of a given structure as possible into suitable disjoint substructures. In a covering problem the task is to cover all elements of a given structure by as few as possible suitable substructures (which are not necessarily disjoint). These problems can be viewed as "duals" of each other. In particular, their solutions sometimes coincide, in which case we obtain a decomposition of the given structure.

A classical example occurs in design theory: under suitable divisibility conditions a Steiner Triple System gives a decomposition of the edges of a complete graph into edge-disjoint triangles, i.e. the optimal solution of the triangle packing problem equals that of the triangle covering problem. Such problems have a long history going back to the 19th century and have many applications, e.g. to testing, statistical design and coding theory.

The project intends to approach long-standing questions concerning optimal packings in non-complete host graphs. These have applications e.g. in communication networks. Another related strand is to study packings and coverings involving more complex structures such as spanning trees and resolvable designs. We intend to provide a powerful algorithmic tool for such questions which can be viewed as near-optimal packing version of the famous Blow-up Lemma. This would have numerous structural and algorithmic applications. Furthermore, the packing and covering viewpoint can be valuable in a much broader context. In particular, we propose to employ it to study the Boolean Satisfiability Problem k-SAT. The k-SAT problem is computationally intractable and of fundamental importance in theoretical computer science. Again, the probabilistic perspective has proved to be invaluable. By formulating the k-SAT problem as a hypergraph covering problem, we will aim to solve key open problems regarding statistical properties of random k-SAT formulas.

Combinatorics is one of the most active areas of research in Mathematics today, focusing on the study of (finite) structures, which take on discrete values. Combinatorics underpins the world of information, such as computers, communication networks and the internet. It also plays a key role in the study of complex networks arising in nature. Partly because of these connections, the field has experienced tremendous growth in the last few decades.
Packings and coverings form a very general framework which can be used to model many (combinatorial) problems. The study of combinatorial packing problems has a long and rich history. To date, a major branch of Combinatorics, called design theory, is devoted to this topic. This has applications to biotechnology, computer science, information theory, and numerical finance. In particular, examples of areas of application in computer science include data mining, the design of parallel algorithms, software testing, database formatting, file organization and interconnection strategies for networks. Examples of other applications in information theory include wireless networking, internet communication protocols, signal processing, and multi-access communications.
The proposed research concerns central open questions on packings and coverings. Its importance is e.g. underlined by the 2008 BIRS final report on the combinatorial design theory workshop which calls the problem to be studied in Objective A1 "one of the next major directions in design theory". Moreover, our objectives in Progamme B will develop a general stand-alone tool for finding near-optimal packings, which would have numerous applications. So we anticipate that the proposed research will have significant impact.

Furthermore, the proposed research lies at the interface between Combinatorics and Computer Science. This is in particular the case for the research proposed in Programme C.
Moreover, as indicated above, the questions studied in Programmes A and B have many applications, e.g. to testing, statistical design and coding theory. So we aim to make our proofs algorithmic, i.e. to provide algorithms which efficiently construct the structures guaranteed by our results. The interface between Combinatorics and Computer Science is a growth area internationally, which is currently underrepresented in the UK. So the project would help to address this deficiency.

As described in the "Academic Impact" section of the Case for support, there is a wide range of research groups, both in the UK and overseas who would benefit from the proposed research. So as described in "Pathways to Impact", we will be disseminating our results as widely and efficiently as possible in order to speed up this process. We believe that we have an excellent track record in this respect.