Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)



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?)

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

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia