×

Local constraints ensuring small representing sets. (English) Zbl 0728.05059

Summary: A set \(T\) is said to cover a set system \({\mathcal F}\) if \(T\) meets all members of \({\mathcal F}\). We raise the following general problem. Find relations among the natural numbers \(p,r,s,t\), that imply the truth of the following statement: If \({\mathcal F}\) is an \(r\)-uniform set system such that each of its subsystems on at most \(p\) elements can be covered with an \(s\)-element set, then \({\mathcal F}\) can be covered with a \(t\)-element set. Here we investigate the case \(s=1\).

MSC:

05D15 Transversal (matching) theory
05A05 Permutations, words, matrices
05B40 Combinatorial aspects of packing and covering
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blokhuis, A., More on maximal intersecting families, J. Combin. Theory Ser. A, 44, 299-303 (1987) · Zbl 0608.05005
[2] Brouwer, A. E.; Schrijver, A., The blocking number of an affine space, J. Combin. Theory Ser. A, 24, 251-253 (1978) · Zbl 0373.05020
[3] Erdős, P.; Gallai, T., On the maximal number of vertices representing the edges of a graph, Magyar Tud. Akad. Mat. Kut. Int. Közl., 6, 181-203 (1961) · Zbl 0101.41001
[4] Jamison, R. E., Covering finite fields with cosets of subspaces, J. Combin. Theory Ser. A, 22, 253-266 (1977) · Zbl 0354.12019
[5] Tuza, Zs., Minimum number of elements representing a set system of given rank, J. Combin. Theory Ser. A, 52, 84-89 (1989) · Zbl 0682.05005
[6] Tuza, Zs., Critical hypergraphs and intersecting set-pair systems, J. Combin. Theory Ser. B, 39, 134-145 (1985) · Zbl 0586.05029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.