×

Simultaneous systems of representatives for families of finite sets. (English) Zbl 0709.05006

Summary: Let \(h\geq 2\) and \(k\geq 1\). Then there exists a real number \(\lambda =\lambda (h,k)\in (0,1)\) such that, if \({\mathcal S}=\{S_ i\}^ s_{i=1}\) and \({\mathcal T}=\{T_ j\}^ t_{j=1}\) are families of nonempty, pairwise disjoint sets with \(| S_ i| \leq h\) and \(| T_ j| \leq k\) and \(S_ i\varsubsetneq T_ j\) for all i and j, then N(\({\mathcal S},{\mathcal T})\leq h^ s\lambda^ t\), where N(\({\mathcal S},{\mathcal T})\) is the number of sets X such that X is a minimal system of representatives for \({\mathcal S}\) and X is simultaneously a system of representatives for \({\mathcal T}\). A conjecture about the best possible value of the constant \(\lambda\) (h,k) is proved in the case \(h>k\). The necessity of the disjointness conditions for the families \({\mathcal S}\) and \({\mathcal T}\) is also demonstrated.

MSC:

05A05 Permutations, words, matrices
11B13 Additive bases, including sumsets
11B75 Other combinatorial number theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Paul Erdős and Melvyn B. Nathanson, Systems of distinct representatives and minimal bases in additive number theory, Number theory, Carbondale 1979 (Proc. Southern Illinois Conf., Southern Illinois Univ., Carbondale, Ill., 1979) Lecture Notes in Math., vol. 751, Springer, Berlin, 1979, pp. 89 – 107. · Zbl 0414.10053
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.