Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 


Specified intersections

Authors: Dhruv Mubayi and Vojtech Rödl
Journal: Trans. Amer. Math. Soc. 366 (2014), 491-504
MSC (2010): Primary 05D05
Published electronically: May 28, 2013
MathSciNet review: 3118403
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ M \subset [n]:=\{0, \ldots , n\}$ and $ {\mathcal {A}}$ be a family of subsets of an $ n$ element set such that $ \vert A \cap B\vert \in M$ for every $ A, B \in \mathcal {A}$. Suppose that $ l$ is the maximum number of consecutive integers contained in $ M$ and $ n$ is sufficiently large. Then

$\displaystyle \vert\mathcal {A}\vert< \min \{1.622^n 10^{2l+5} \, ,\quad 2^{n/2+l\log ^2 n}\}.$

The first bound complements the previous bound of roughly $ (1.99)^n$ due to Frankl and the second author which was proved under the assumption that $ M=[n]\setminus \{n/4\}$. For $ l=o(n/\log ^2 n)$, the second bound above becomes better than the first bound. In this case, it yields $ 2^{n/2+o(n)}$, 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 $ 2^{n/2+o(n)}$ remains valid as long as $ l<n/10$.

Our second result complements the result of Frankl and the second author in a different direction. Fix $ \varepsilon >0$ and $ \varepsilon n < t<n/5$ and let $ M=[n]\setminus (t, t+n^{0.525})$. Then, in the notation above, we prove that for $ n$ sufficiently large,

$\displaystyle \vert\mathcal {A}\vert \le n{n \choose (n+t)/2}.$

This is essentially sharp, aside from the multiplicative factor of $ n$. The short proof uses the Frankl-Wilson theorem and results about the distribution of prime numbers. We conjecture that a similar bound holds for $ M=[n]\setminus \{t\}$ whenever $ \varepsilon n < t < n/3$. A similar conjecture when $ t$ is fixed and $ n$ is large was made earlier by Frankl (1977) and proved by Frankl and Füredi (1984).

References [Enhancements On Off] (What's this?)

  • 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 $ \ell _1$ 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)

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

Vojtech Rödl
Affiliation: Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30322

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 DMS-0969092
The second author’s research was supported in part by NSF grant DMS-0800070
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society