Forbidden intersections

Source abstract

About ten years ago P. Erdös conjectured that if F \mathcal {F} is a family of subsets of { 1 , 2 , … , n } \{ 1,2, \ldots ,n\} without F F , F ′ ∈ F F’ \in \mathcal {F} , | F ∩ F ′ | = [ n / 4 ] |F \cap F’| = [n/4] , then | F | > ( 2 − ε ) n |\mathcal {F}| > {(2 - \varepsilon )^n} holds for some positive absolute constant ε \varepsilon . Here this conjecture is proved in a stronger form (Theorem 1.1), which solves a \mathdollar 250 problem of Erdös. Suppose C \mathcal {C} is a code (i.e., a collection of sequences of length n n ) over an alphabet of q q elements, where 1 2 > δ > 0 \tfrac {1} {2} > \delta > 0 is arbitrary. Suppose further that there are no two codewords at Hamming distance d d where d d is a fixed integer, δ n > d > ( 1 − δ ) n \delta n > d > (1 - \delta )n , and d d is even if q = 2 q = 2 . Then | C | > ( q − ε ) n |\mathcal {C}| > {(q - \varepsilon )^n} , where ε > 0 \varepsilon > 0 depends only on q q and δ \delta . The following conjecture of Erdös and Szemerédi is also proved: If F \mathcal {F} is a family of subsets of { 1 , 2 , … , n } \{ 1,2, \ldots ,n\} not containing a weak Δ \Delta -system of size r r (cf. Definition 1.8), then | F | > ( 2 − ε r ) n |\mathcal {F}| > {(2 - {\varepsilon _r})^n} , ε r > 0 {\varepsilon _r} > 0 holds. An old conjecture of Larman and Rogers is established in the following stronger form: Let A \mathcal {A} be a collection of 4 n 4n -dimensional ( ± 1 ) ( \pm 1) -vectors, r ⩾ 2 r \geqslant 2 is a fixed integer. Suppose that A A does not contain r r pairwise orthogonal vectors. Then | A | > ( 2 − ε ) 4 n |\mathcal {A}| > {(2 - \varepsilon )^{4n}} . All these results can be deduced from our most general result (Theorem 1.16) which concerns the intersection pattern of families of partitions. This result has further implications in Euclidean Ramsey theory as well as for isometric embeddings into the Hamming space H ( n , q ) H(n,q) (cf. Theorem 9.1).