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
DOI: https://doi.org/10.1090/S0002-9939-1971-0270924-9
MathSciNet review: 0270924
Full-text PDF

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özy and E. Szemerédi, On the solvability of the equations, $ [{a_i},{a_j}] = {a_r}$ and $ ({a'_i},{a'_j}) = {a'_r}$ in sequences of positive density, J. Math. Anal. Appl. 15 (1966), 60-64. MR 33 #4035. 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. MR 21 #63. MR 0101250 (21:63)
  • [4] D. J. Kleitman, On a lemma of Littlewood and Offord on the distribution of certain sums, Math. Z. 90 (1965), 251-259. MR 32 #2336. 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-216. See also: P. Erdös, J. London Math. Soc. 19 (1944), 208. MR 3, 270; MR 7, 242. MR 0006197 (3:270e)
  • [6] R. K. Guy and S. Znám, A problem of Zarankiewicz, Recent Progress in Combinatorics, 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

DOI: https://doi.org/10.1090/S0002-9939-1971-0270924-9
Keywords: Bounds on collection size, sizes of subset families
Article copyright: © Copyright 1971 American Mathematical Society

American Mathematical Society