Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Simultaneous systems of representatives for families of finite sets

Author: Melvyn B. Nathanson
Journal: Proc. Amer. Math. Soc. 103 (1988), 1322-1326
MSC: Primary 05A05
MathSciNet review: 955030
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ h \geq 2$ and $ k \geq 1$. Then there exists a real number $ \lambda = \lambda \left( {h,k} \right) \in \left( {0,1} \right)$ such that, if $ \mathcal{S} = \left\{ {{S_i}} \right\}_{i = 1}^s$ and $ \mathcal{T} = \left\{ {{T_j}} \right\}_{j = 1}^t$ are families of nonempty, pairwise disjoint sets with $ \vert{{S_i}}\vert \leq h$ and $ \vert{{T_j}}\vert \leq k$ and $ {S_i} \nsubseteq {T_j}$ for all $ i$ and $ j$, then $ N\left( {\mathcal{S},\mathcal{T}} \right) \leq {h^s}{\lambda ^t}$, where $ N\left( {\mathcal{S},\mathcal{T}} \right)$ 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 \left( {h,k} \right)$ is proved in the case $ h > k$. The necessity of the disjointness conditions for the families $ \mathcal{S}$ and $ \mathcal{T}$ is also demonstrated.

References [Enhancements On Off] (What's this?)

  • [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. MR 564925

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05A05

Retrieve articles in all journals with MSC: 05A05

Additional Information

Keywords: Systems of representatives, additive bases
Article copyright: © Copyright 1988 American Mathematical Society