Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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 Free Access

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 (81k:10089)

Similar Articles

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

Retrieve articles in all journals with MSC: 05A05


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9939-1988-0955030-2
PII: S 0002-9939(1988)0955030-2
Keywords: Systems of representatives, additive bases
Article copyright: © Copyright 1988 American Mathematical Society