Specified intersections
Authors:
Dhruv Mubayi and Vojtech Rödl
Journal:
Trans. Amer. Math. Soc. 366 (2014), 491504
MSC (2010):
Primary 05D05
Published electronically:
May 28, 2013
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let and be a family of subsets of an element set such that for every . Suppose that is the maximum number of consecutive integers contained in and is sufficiently large. Then The first bound complements the previous bound of roughly due to Frankl and the second author which was proved under the assumption that . For , the second bound above becomes better than the first bound. In this case, it yields , and this can be viewed as a generalization (in an asymptotic sense) of the famous Eventown theorem of Berlekamp (1969) and Graver (1975). We conjecture that our bound remains valid as long as . Our second result complements the result of Frankl and the second author in a different direction. Fix and and let . Then, in the notation above, we prove that for sufficiently large, This is essentially sharp, aside from the multiplicative factor of . The short proof uses the FranklWilson theorem and results about the distribution of prime numbers. We conjecture that a similar bound holds for whenever . A similar conjecture when is fixed and is large was made earlier by Frankl (1977) and proved by Frankl and Füredi (1984).
 1.
R.
C. Baker, G.
Harman, and J.
Pintz, The difference between consecutive primes. II, Proc.
London Math. Soc. (3) 83 (2001), no. 3,
532–562. MR 1851081
(2002f:11125), http://dx.doi.org/10.1112/plms/83.3.532
 2.
E.
R. Berlekamp, On subsets with intersections of even
cardinality, Canad. Math. Bull. 12 (1969),
471–474. MR 0249303
(40 #2549)
 3.
Harry
Buhrman, Richard
Cleve, and Avi
Wigderson, Quantum vs. classical communication and
computation, STOC ’98 (Dallas, TX), ACM, New York, 1999,
pp. 63–68. MR
1731563
 4.
P.
Erdős, Problems and results in graph theory and
combinatorial analysis, Proceedings of the Fifth British Combinatorial
Conference (Univ. Aberdeen, Aberdeen, 1975), Utilitas Math., Winnipeg,
Man., 1976, pp. 169–192. Congressus Numerantium, No. XV. MR 0409246
(53 #13006)
 5.
P.
Erdős and E.
Szemerédi, Combinatorial properties of systems of sets,
J. Combinatorial Theory Ser. A 24 (1978), no. 3,
308–313. MR 0491202
(58 #10467)
 6.
P.
Frankl, An intersection problem for finite sets, Acta Math.
Acad. Sci. Hungar. 30 (1977), no. 34, 371–373.
MR
0457224 (56 #15435)
 7.
P.
Frankl and Z.
Füredi, On hypergraphs without two edges intersecting in a
given number of vertices, J. Combin. Theory Ser. A 36
(1984), no. 2, 230–236. MR 734980
(86a:05091), http://dx.doi.org/10.1016/00973165(84)900086
 8.
Peter
Frankl and Zoltán
Füredi, Forbidding just one intersection, J. Combin.
Theory Ser. A 39 (1985), no. 2, 160–176. MR 793269
(86j:05008), http://dx.doi.org/10.1016/00973165(85)900354
 9.
Peter
Frankl and Vojtěch
Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), no. 1, 259–286. MR 871675
(88m:05003), http://dx.doi.org/10.1090/S00029947198708716756
 10.
P.
Frankl and N.
M. Singhi, Linear dependencies among subsets of a finite set,
European J. Combin. 4 (1983), no. 4, 313–318.
MR 743153
(85j:05001)
 11.
P.
Frankl and R.
M. Wilson, Intersection theorems with geometric consequences,
Combinatorica 1 (1981), no. 4, 357–368. MR 647986
(84g:05085), http://dx.doi.org/10.1007/BF02579457
 12.
Jack
E. Graver, Boolean designs and selfdual matroids, Linear
Algebra and Appl. 10 (1975), 111–128. MR 0376400
(51 #12576)
 13.
Hamed
Hatami, Avner
Magen, and Evangelos
Markakis, Integrality gaps of semidefinite programs for vertex
cover and relations to 𝑙₁ embeddability of negative type
metrics, SIAM J. Discrete Math. 23 (2008/09),
no. 1, 178–194. MR 2476821
(2009m:90098), http://dx.doi.org/10.1137/070700103
 14.
Gy.
Katona, Intersection theorems for systems of finite sets, Acta
Math. Acad. Sci. Hungar 15 (1964), 329–337. MR 0168468
(29 #5731)
 15.
Jon
Kleinberg and Michel
X. Goemans, The Lovász theta function and a semidefinite
programming relaxation of vertex cover, SIAM J. Discrete Math.
11 (1998), no. 2, 196–204 (electronic). MR 1617152
(99b:90104), http://dx.doi.org/10.1137/S0895480195287541
 16.
D.
G. Larman and C.
A. Rogers, The realization of distances within sets in Euclidean
space, Mathematika 19 (1972), 1–24. MR 0319055
(47 #7601)
 17.
Jiří
Sgall, Bounds on pairs of families with restricted
intersections, Combinatorica 19 (1999), no. 4,
555–566. MR 1773657
(2001e:05135), http://dx.doi.org/10.1007/s004939970007
 1.
 R. C. Baker, G. Harman, J. Pintz, The difference between consecutive primes. II. Proc. London Math. Soc. (3) 83 (2001), no. 3, 532562. MR 1851081 (2002f:11125)
 2.
 E. R. Berlekamp, On subsets with intersections of even cardinality, Canad. Math. Bull. 12 (1969), 363366. MR 0249303 (40:2549)
 3.
 H. Buhrman, R. Cleve, A. Wigderson, Quantum vs. Classical Communication and Computation, Proceedings of 30th STOC, pp. 6368, 1998. MR 1731563
 4.
 P. Erdős, Problems and results in graph theory and combinatorial analysis, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congress. Numer. XV, pp. 169192, Utilitas Math., Winnipeg, Man., 1976. MR 0409246 (53:13006)
 5.
 P. Erdős, E. Szemerédi, Combinatorial properties of systems of sets. J. Combinatorial Theory Ser. A 24 (1978), no. 3, 308313. MR 0491202 (58:10467)
 6.
 P. Frankl, An intersection problem for finite sets, Acta Math. Acad. Sci. Hungar. 30 (1977), no. 34, 371373. MR 0457224 (56:15435)
 7.
 P. Frankl, Z. Füredi, On hypergraphs without two edges intersecting in a given number of vertices, J. Combin. Theory Ser. A 36 (1984), no. 2, 230236. MR 734980 (86a:05091)
 8.
 P. Frankl, Z. Füredi, Forbidding just one intersection, J. Combin. Theory Ser. A 39 (1985), no. 2, 160176. MR 793269 (86j:05008)
 9.
 P. Frankl, V. Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), no. 1, 259286. MR 871675 (88m:05003)
 10.
 P. Frankl, N. Singhi, Linear dependencies among subsets of a finite set, European J. Combin. 4 (1983), no. 4, 313318. MR 743153 (85j:05001)
 11.
 P. Frankl, R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981) 357368. MR 647986 (84g:05085)
 12.
 J. E. Graver, Boolean designs and selfdual matroids, Lin Alg. Appl. 10 (1975), 111128. MR 0376400 (51:12576)
 13.
 H. Hatami, Avner Magen and Vangelis Markakis, Integrality gaps of semidefinite programs for Vertex Cover and relations to embeddability of Negative type metrics, SIAM Journal on Discrete Mathematics, 23(1) (2008/09), 178194. MR 2476821 (2009m:90098)
 14.
 Gy. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar 15 1964 329337. MR 0168468 (29:5731)
 15.
 J. Kleinberg, M. Goemans. The Lovasz theta function and a semidefinite programming relaxation of vertex cover. SIAM J. Discrete Math, 11 (1998) 196204. MR 1617152 (99b:90104)
 16.
 D. Larman, C. Rogers, The realization of distances within sets in Euclidean space. Mathematika 19 (1972), 124. MR 0319055 (47:7601)
 17.
 J. Sgall, Bounds on pairs of families with restricted intersections, Combinatorica 19 (1999), no. 4, 555566. MR 1773657 (2001e:05135)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2010):
05D05
Retrieve articles in all journals
with MSC (2010):
05D05
Additional Information
Dhruv Mubayi
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, Illinois 60607
Email:
mubayi@uic.edu
Vojtech Rödl
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322
Email:
rodl@mathcs.emory.edu
DOI:
http://dx.doi.org/10.1090/S000299472013058771
PII:
S 00029947(2013)058771
Received by editor(s):
January 1, 1928
Received by editor(s) in revised form:
May 14, 2012, and January 1, 2011
Published electronically:
May 28, 2013
Additional Notes:
The first author’s research was supported in part by NSF grant DMS0969092
The second author’s research was supported in part by NSF grant DMS0800070
Article copyright:
© Copyright 2013 American Mathematical Society
