Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
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
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
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/S0002-9947-2013-05877-1
PII: S 0002-9947(2013)05877-1
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