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 finite families of finite sets

Author: Xing De Jia
Journal: Proc. Amer. Math. Soc. 104 (1988), 33-36
MSC: Primary 05A05; Secondary 11B99
MathSciNet review: 958037
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ h \geq 2$ and $ k \geq 1$. It is proved that if $ \mathcal{S} = \{ {S_i}\} _{i = 1}^s$ and $ \mathcal{T} = \{ {T_j}\} _{j = 1}^t$ are two families of nonempty, pairwise disjoint sets such that $ \vert{S_i}\vert \leq h,\vert{T_j}\vert \leq k$ and $ {S_i} \nsubseteq {T_j}$ for all $ i$ and $ j$, then the number $ N(\mathcal{S},\mathcal{T})$ of the 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}$ that satisfies $ N(\mathcal{S},\mathcal{T}) \leq {h^s}{(1 - (h - r)/{h^{q + 1}})^t}$, where $ k = q(h - 1) + r$ with $ 0 \leq r \leq h - 2$. This was conjectured by M. B. Nathanson [3] in 1985.

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

  • [1] P. Erdös and M. B. Nathanson, Systems of distinct representatives and minimal bases in additive number theory, Number Theory, Carbondale 1979 (M. B. Nathanson, ed.), Lecture Notes in Math., vol. 751, Springer-Verlag, Berlin and New York, 1979, pp. 89-107. MR 564925 (81k:10089)
  • [2] Jia Xing-De, On an open combinatorial problem of Erdös and Nathanson, Chinese Ann. Math. (to appear).
  • [3] M. B. Nathanson, Simultaneous systems of representatives for families of finite sets, Proc. Amer. Math. Soc. (to appear). MR 955030 (90b:05002)

Similar Articles

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

Retrieve articles in all journals with MSC: 05A05, 11B99

Additional Information

Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society