Specified intersections

Authors:
Dhruv Mubayi and Vojtech Rödl

Journal:
Trans. Amer. Math. Soc. **366** (2014), 491-504

MSC (2010):
Primary 05D05

DOI:
https://doi.org/10.1090/S0002-9947-2013-05877-1

Published electronically:
May 28, 2013

MathSciNet review:
3118403

Full-text 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

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,

**1.**R. C. Baker, G. Harman, J. Pintz, The difference between consecutive primes. II. Proc. London Math. Soc. (3) 83 (2001), no. 3, 532-562. MR**1851081 (2002f:11125)****2.**E. R. Berlekamp, On subsets with intersections of even cardinality, Canad. Math. Bull. 12 (1969), 363-366. MR**0249303 (40:2549)****3.**H. Buhrman, R. Cleve, A. Wigderson, Quantum vs. Classical Communication and Computation, Proceedings of 30th STOC, pp. 63-68, 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. 169-192, 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, 308-313. MR**0491202 (58:10467)****6.**P. Frankl, An intersection problem for finite sets, Acta Math. Acad. Sci. Hungar. 30 (1977), no. 3-4, 371-373. 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, 230-236. MR**734980 (86a:05091)****8.**P. Frankl, Z. Füredi, Forbidding just one intersection, J. Combin. Theory Ser. A 39 (1985), no. 2, 160-176. MR**793269 (86j:05008)****9.**P. Frankl, V. Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), no. 1, 259-286. MR**871675 (88m:05003)****10.**P. Frankl, N. 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, R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981) 357-368. MR**647986 (84g:05085)****12.**J. E. Graver, Boolean designs and self-dual matroids, Lin Alg. Appl. 10 (1975), 111-128. 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), 178-194. MR**2476821 (2009m:90098)****14.**Gy. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar 15 1964 329-337. MR**0168468 (29:5731)****15.**J. Kleinberg, M. Goemans. The Lovasz theta function and a semi-definite programming relaxation of vertex cover. SIAM J. Discrete Math, 11 (1998) 196-204. MR**1617152 (99b:90104)****16.**D. Larman, C. Rogers, The realization of distances within sets in Euclidean space. Mathematika 19 (1972), 1-24. MR**0319055 (47:7601)****17.**J. Sgall, Bounds on pairs of families with restricted intersections, Combinatorica 19 (1999), no. 4, 555-566. MR**1773657 (2001e:05135)**

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:
https://doi.org/10.1090/S0002-9947-2013-05877-1

Received by editor(s):
January 1, 2028

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 DMS-0969092

The second author’s research was supported in part by NSF grant DMS-0800070

Article copyright:
© Copyright 2013
American Mathematical Society