Covering and packing

Combinatorial configurations related to multi-valued mappings of one set into another. Assume that one is given sets $ V $ and $ E $ together with a multi-valued mapping $ \Gamma $ of $ E $ into $ V $. Let $ \Gamma ( e) $ be the image of an element $ e \in E $ under $ \Gamma $ and, for any $ C \subseteq E $, let $ \Gamma ( C) = \cup _ {e \in E } \Gamma ( e) $. A subset $ C \subseteq E $ is called a covering for $ ( V, E, \Gamma ) $ if $ \Gamma ( C) = V $. A subset $ P \subseteq E $ is called a packing for $ ( V, E, \Gamma ) $ if for any two different elements $ e _ {i} $ and $ e _ {j} $ from $ P $ the sets $ \Gamma ( e _ {i} ) $ and $ \Gamma ( e _ {j} ) $ do not intersect. A subset $ P \subseteq E $ is called a perfect packing, or a perfect covering, if $ P $ is simultaneously a covering and a packing. The set $ E $ is called the covering set, and the set $ V $ is called the covered set. If the inverse mapping $ \Gamma ^ {-} 1 $ is such that $ \Gamma ^ {-} 1 ( V) = E $, one can consider $ V $ as a covering set and $ E $ as the covered set. The mapping $ \Gamma : E \rightarrow V $ defines an incidence relation $ I $ for which $ v $ from $ V $ and $ e $ from $ E $ are incident (denoted by $ vIe $) if $ v \in \Gamma ( e) $.

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

$$ \max _ {e \in E } | \Gamma ( e) | \leq u ,\ \ \min _ {v \in V } | \Gamma ^ {-} 1 ( v) | \geq w, $$

then the minimum cardinality $ \kappa ( V, E, \Gamma ) $ of the covering satisfies the inequalities

$$ \frac{| V | }{u} \leq \ \kappa ( V, E, \Gamma ) \leq \ 1 + \frac{E}{w} \left ( \frac{ \mathop{\rm ln} | V | w }{| E | } \right ) . $$

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

Sometimes a function $ \lambda $ is defined on the covered set $ V $ that takes non-negative integer values, and then the name $ \lambda $- covering ( $ \lambda $- packing) is given to a subset $ P \subseteq E $ that satisfies the following condition: For each $ v \in V $, the number $ \sigma ( v, P) $ of those elements $ e \in P $ that are incident to $ v $ obeys the inequality

$$ \sigma ( v, P) \geq \lambda ( v) $$

(correspondingly, $ \sigma ( v, P) \leq \lambda ( v) $). There is a relationship between $ \lambda $- coverings of minimal cardinality and $ \lambda $- packings of maximal cardinality. That is, let two sets $ V $ and $ E $ be given together with a multi-valued mapping $ \Gamma : E \rightarrow V $ and let also functions $ \lambda $ and $ \lambda ^ \prime $ be given on $ V $ such that for each $ v \in V $,

$$ \lambda ( v) + \lambda ^ \prime ( v) = \ | \Gamma ^ {-} 1 ( v) | . $$

Then, if the set $ C $ is a $ \lambda $- covering of minimal cardinality for $ ( V, E, \Gamma ) $, the set $ P = E \setminus C $ is a $ \lambda ^ \prime $- packing of maximal cardinality, and vice versa. If $ P $ is a maximal $ \lambda ^ \prime $- packing, the set $ C = E \setminus P $ is a $ \lambda $- covering of minimal cardinality. The following relate, for example, to the class of problems concerned with coverings and packings:

1) Let $ G $ be a graph with set of vertices $ V $ and set of edges $ E $. If one considers $ V $ as the covered set and $ E $ as the covering set, while the incidence relation for the vertices and edges is taken as $ I $, 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 $ I $ 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 $ V $ be a non-empty set in a metric space $ R $. A system $ \pi $ of sets $ U \subseteq R $ is called an $ \epsilon $- covering of $ V $ if the diameter $ d( U) $ of any set $ U \in \pi $ does not exceed $ 2 \epsilon $ and $ V \subseteq \cup _ {U \in \pi } U $. A set $ S \subseteq R $ is called an $ \epsilon $- net for $ V $ if any point in the set $ V $ is at distance not exceeding $ \epsilon $ from some point in $ S $. A set $ U \subseteq R $ is called $ \epsilon $- distinguishable if any two of different points of it have distance greater than $ \epsilon $. Let $ N _ \epsilon ( V) $ be the minimal number of sets in an $ \epsilon $- covering of $ V $, and let $ M _ \epsilon ( V) $ be the maximal number of points in an $ \epsilon $- distinguishable subset of $ V $. The number $ \mathop{\rm log} _ {2} N _ \epsilon ( V) $ is called the $ \epsilon $- entropy of $ V $, while $ \mathop{\rm log} _ {2} M _ \epsilon ( V) $ is called the $ \epsilon $- capacity of $ V $. The concepts of $ \epsilon $- entropy and $ \epsilon $- capacity are used in the theory of approximation of functions and in information theory.

3) Let $ B ^ {n} $ be the $ n $- 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 $ r $ in $ B ^ {n} $. Then the set of centres for the sphere packing is a code that will correct $ r $ 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 $ N _ {f} $ of vertices in the cube $ B ^ {n} $ on which some Boolean function $ f( x _ {1} \dots x _ {n} ) $ takes the value 1, while the covering set is the set of faces (intervals) entirely contained in $ N _ {f} $, then the covering of minimal cardinality will correspond to the shortest disjunctive normal form of $ f( x _ {1} \dots x _ {n} ) $, while the covering with minimal sum of ranks will correspond to the minimal disjunctive normal form of $ f( x _ {1} \dots x _ {n} ) $( 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) MR0172183 Zbl 0176.51401
[2]	L. Fejes Toth, "Lagerungen in der Ebene, auf der Kugel und im Raum" , Springer (1972) Zbl 0229.52009
[3]	W.W. Peterson, E.J. Weldon, "Error-correcting codes" , M.I.T. (1972) MR0347444 Zbl 0251.94007
[4]	, Discrete mathematics and mathematical problems in cybernetics , 1 , Moscow (1974) (In Russian) Zbl 1185.68346
[5]	F. Harary, "Graph theory" , Addison-Wesley (1972) MR1536844 Zbl 1161.05345 Zbl 0951.05056 Zbl 0838.05066 Zbl 0854.05044 Zbl 0797.05064 Zbl 0677.01013 Zbl 0547.00012 Zbl 0443.05036 Zbl 0471.05024 Zbl 0465.05026 Zbl 0458.00002 Zbl 0329.05125 Zbl 0288.05109 Zbl 0282.00003 Zbl 0275.05101 Zbl 0253.00004 Zbl 0224.05129 Zbl 0196.27202 Zbl 0193.28103 Zbl 0182.57702
[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) MR0112032
[9]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian) MR0362811 Zbl 0524.65001
[10]	S.V. Yablonskii, "Introduction to discrete mathematics" , Moscow (1979) (In Russian) MR0563327

References

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