Specified intersections

DOI10.1090/S0002-9947-2013-05877-1MaRDI QIDQ2862137zbMATH OpenOpenAlexFDO

Authors Dhruv Mubayi, Vojtěch Rödl

Publication date 14 November 2013

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.5651

zbMATH Keywords

family of subsets maximum number of consecutive integers

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Let M be a subset of {0, .., n} and F be a family of subsets of an n element set such that the size of A intersection B is in M for every A, B in F. Suppose that l is the maximum number of consecutive integers contained in M and n is sufficiently large. Then we prove that |F| < min {1.622^n 100^l, 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 applies even when M={0, 1,.., n} - {n/4}. For small l, 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. Our second result complements the result of Frankl-Rodl in a different direction. Fix eps>0 and eps n < t < n/5 and let M={0, 1, .., n)-(t, t+n^{0.525}). Then, in the notation above, we prove that for n sufficiently large, |F| < 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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Specified intersections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2862137)