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?)

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