Covering and packing

Combinatorial configurations related to multi-valued mappings of one set into another. Assume that one is given sets and together with a multi-valued mapping of into . Let be the image of an element under and, for any , let . A subset is called a covering for if . A subset is called a packing for if for any two different elements and from the sets and do not intersect. A subset is called a perfect packing, or a perfect covering, if is simultaneously a covering and a packing. The set is called the covering set, and the set is called the covered set. If the inverse mapping is such that , one can consider as a covering set and as the covered set. The mapping defines an incidence relation for which from and from are incident (denoted by ) if .

The concepts of a packing and a covering are related to extremal problems involving the search for packings and coverings (for any given triple ) that provide an extremum for some functional. That functional may, for example, be specified by means of a function that puts each element from into correspondence with a non-negative real number , called the weight of the element . The minimal covering problem consists in constructing a covering for which takes a minimal value. One often considers the case where ; here one is concerned with finding a covering of minimal cardinality, or a so-called least covering. If the triple is such that

then the minimum cardinality of the covering satisfies the inequalities

In extremal problems on packings one usually is required to find packings of maximal cardinality.

Sometimes a function is defined on the covered set that takes non-negative integer values, and then the name -covering (-packing) is given to a subset that satisfies the following condition: For each , the number of those elements that are incident to obeys the inequality

(correspondingly, ). There is a relationship between -coverings of minimal cardinality and -packings of maximal cardinality. That is, let two sets and be given together with a multi-valued mapping and let also functions and be given on such that for each ,

Then, if the set is a -covering of minimal cardinality for , the set is a -packing of maximal cardinality, and vice versa. If is a maximal -packing, the set is a -covering of minimal cardinality. The following relate, for example, to the class of problems concerned with coverings and packings:

1) Let be a graph with set of vertices and set of edges . If one considers as the covered set and as the covering set, while the incidence relation for the vertices and edges is taken as , a covering is an edge-covering of the graph and a packing is a pairing, while a perfect packing is a perfect pairing. If one takes the set of vertices as the covering and covered sets, while is the adjacency relation for vertices, a covering will be an externally stable set, while a packing is an internally stable set; moreover, the cardinality of the minimal covering is the external stability number, and the cardinality of the maximum packing is the internal stability number (see Graph, numerical characteristics of a).

2) Let be a non-empty set in a metric space . A system of sets is called an -covering of if the diameter of any set does not exceed and . A set is called an -net for if any point in the set is at distance not exceeding from some point in . A set is called -distinguishable if any two of different points of it have distance greater than . Let be the minimal number of sets in an -covering of , and let be the maximal number of points in an -distinguishable subset of . The number is called the -entropy of , while is called the -capacity of . The concepts of -entropy and -capacity are used in the theory of approximation of functions and in information theory.

3) Let be the -dimensional unit cube with the Hamming metric, while the covered set is the set of its vertices and the covering set is the set of spheres of radius in . Then the set of centres for the sphere packing is a code that will correct errors. If the packing is perfect, the code is said to be densely packed or perfect.

If for the covered set one takes the subset of vertices in the cube on which some Boolean function takes the value 1, while the covering set is the set of faces (intervals) entirely contained in , then the covering of minimal cardinality will correspond to the shortest disjunctive normal form of , while the covering with minimal sum of ranks will correspond to the minimal disjunctive normal form of (see Boolean functions, normal forms of).

In problems on coverings and packings, one estimates their cardinality, examines questions of existence, construction and enumeration of perfect packings, as well as the possibility of constructing effective algorithms for solving these problems.

References

[1]	C.A. Rogers, "Packing and covering" , Cambridge Univ. Press (1964)
[2]	L. Fejes Toth, "Lagerungen in der Ebene, auf der Kugel und im Raum" , Springer (1972)
[3]	W.W. Peterson, E.J. Weldon, "Error-correcting codes" , M.I.T. (1972)
[4]	, Discrete mathematics and mathematical problems in cybernetics , 1 , Moscow (1974) (In Russian)
[5]	F. Harary, "Graph theory" , Addison-Wesley (1972)
[6]	C. Berge, "Théorie des graphes et leurs applications" , Dunod (1958)
[7]	A.G. Vitushkin, "Estimation of the complexity of the tabulation problem" , Moscow (1959) (In Russian)
[8]	A.N. Kolmogorov, V.M. Tikhomirov, "-entropy and -capacity of sets in function spaces" Uspekhi Mat. Nauk , 14 : 2 (1959) pp. 3–86 (In Russian)
[9]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[10]	S.V. Yablonskii, "Introduction to discrete mathematics" , Moscow (1979) (In Russian)

References

[a1]	A. Schrijver (ed.) , Packing and covering in combinatorics , CWI , Amsterdam (1979)