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)



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
  • [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
  • [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
  • [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
  • [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

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

Keywords: Bounds on collection size, sizes of subset families
Article copyright: © Copyright 1971 American Mathematical Society