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)



Forbidden intersections

Authors: Peter Frankl and Vojtěch Rödl
Journal: Trans. Amer. Math. Soc. 300 (1987), 259-286
MSC: Primary 05A05; Secondary 94B25
MathSciNet review: 871675
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: About ten years ago P. Erdös conjectured that if $ \mathcal{F}$ is a family of subsets of $ \{ 1,2, \ldots ,n\} $ without $ F$, $ F' \in \mathcal{F}$, $ \vert F \cap F'\vert = [n/4]$, then $ \vert\mathcal{F}\vert < {(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 250 problem of Erdös. Suppose $ \mathcal{C}$ is a code (i.e., a collection of sequences of length $ n$) over an alphabet of $ q$ elements, where $ \tfrac{1} {2} > \delta > 0$ is arbitrary. Suppose further that there are no two codewords at Hamming distance $ d$ where $ d$ is a fixed integer, $ \delta n < d < (1 - \delta )n$, and $ d$ is even if $ q = 2$. Then $ \vert\mathcal{C}\vert < {(q - \varepsilon )^n}$, where $ \varepsilon > 0$ depends only on $ q$ and $ \delta $.

The following conjecture of Erdös and Szemerédi is also proved: If $ \mathcal{F}$ is a family of subsets of $ \{ 1,2, \ldots ,n\} $ not containing a weak $ \Delta $-system of size $ r$ (cf. Definition 1.8), then $ \vert\mathcal{F}\vert < {(2 - {\varepsilon _r})^n}$, $ {\varepsilon _r} > 0$ holds.

An old conjecture of Larman and Rogers is established in the following stronger form: Let $ \mathcal{A}$ be a collection of $ 4n$-dimensional $ ( \pm 1)$-vectors, $ r \geqslant 2$ is a fixed integer. Suppose that $ A$ does not contain $ r$ pairwise orthogonal vectors. Then $ \vert\mathcal{A}\vert < {(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)$ (cf. Theorem 9.1).

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

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05A05, 94B25

Retrieve articles in all journals with MSC: 05A05, 94B25

Additional Information

Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society