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)

On collections of subsets containing no $ 4$-member Boolean algebra.

Authors: Paul Erdős and Daniel Kleitman
Journal: Proc. Amer. Math. Soc. 28 (1971), 87-90
MSC: Primary 05.04
MathSciNet review: 0270924
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, upper and lower bounds each of the form $ c{2^n}/{n^{1/4}}$ are obtained for the maximum possible size of a collection $ Q$ of subsets of an $ n$ element set satisfying the restriction that no four distinct members $ A,B,C,D$ of $ Q$ satisfy $ A \bigcup B = C$ and $ A \bigcap B = D$.

The lower bound is obtained by a construction while the upper bound is obtained by applying a somewhat weaker condition on $ Q$ which leads easily to a bound. Probably there is an absolute constant $ c$ so that

$\displaystyle \max \vert Q\vert = c{2^n}/{n^{1/4}} + o({2^n}/{n^{1/4}})$

but we cannot prove this and have no guess at what the value of $ c$ is.

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

  • [1] P. Erdős, A. Sárközi, and E. Szemerédi, On the solvability of the equations [𝑎ᵢ,𝑎ⱼ]=𝑎ᵣ and (𝑎ᵢ′,𝑎ⱼ′)=𝑎ᵣ′ in sequences of positive density, J. Math. Anal. Appl. 15 (1966), 60–64. MR 0195837 (33 #4035)
  • [2] K. Zarankiewicz, Problem $ P$ 101, Colloq. Math. 2 (1951), 301. See also: R. K. Guy, A problem of Zarankiewicz, Proc. Colloq. Theory of Graphs (Tihany, 1966), Akad. Kiadó, Budapest, 1968, pp. 119-150.
  • [3] I. Reiman, Über ein Problem von K. Zarankiewicz, Acta. Math. Acad. Sci. Hungar. 9 (1958), 269–273 (German). MR 0101250 (21 #63)
  • [4] Daniel J. Kleitman, On a lemma of Littlewood and Offord on the distribution of certain sums, Math. Z. 90 (1965), 251–259. MR 0184865 (32 #2336)
  • [5] P. Erdös and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215. MR 0006197 (3,270e)
  • [6] Richard K. Guy and Štefan Znám, A problem of Zarankiewicz, Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), Academic Press, New York, 1969, pp. 237–243. MR 0256902 (41 #1557)

Similar Articles

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

Retrieve articles in all journals with MSC: 05.04

Additional Information

PII: S 0002-9939(1971)0270924-9
Keywords: Bounds on collection size, sizes of subset families
Article copyright: © Copyright 1971 American Mathematical Society