On collections of subsets containing no member Boolean algebra.
Authors:
Paul Erdős and Daniel Kleitman
Journal:
Proc. Amer. Math. Soc. 28 (1971), 8790
MSC:
Primary 05.04
MathSciNet review:
0270924
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In this paper, upper and lower bounds each of the form are obtained for the maximum possible size of a collection of subsets of an element set satisfying the restriction that no four distinct members of satisfy and . The lower bound is obtained by a construction while the upper bound is obtained by applying a somewhat weaker condition on which leads easily to a bound. Probably there is an absolute constant so that but we cannot prove this and have no guess at what the value of is.
 [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 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. 119150.
 [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)
 [1]
 P. Erdös, A. Sárközy and E. Szemerédi, On the solvability of the equations, and in sequences of positive density, J. Math. Anal. Appl. 15 (1966), 6064. MR 33 #4035. MR 0195837 (33:4035)
 [2]
 K. Zarankiewicz, Problem 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. 119150.
 [3]
 I. Reiman, Über ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar. 9 (1958), 269273. 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), 251259. 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), 212216. 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. 237243. 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:
http://dx.doi.org/10.1090/S00029939197102709249
PII:
S 00029939(1971)02709249
Keywords:
Bounds on collection size,
sizes of subset families
Article copyright:
© Copyright 1971 American Mathematical Society
