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
DOI: https://doi.org/10.1090/S0002-9947-1987-0871675-6
MathSciNet review: 871675
Full-text PDF Free Access

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

  • [A] N. Alon (personal communication).
  • [AGP] R. Ahlswede, A. El Gamal and K. F. Pang, A two-family extremal problem in Hamming space, Discrete Math. 49 (1984), 1-5. MR 737611 (86c:05005)
  • [AK] R. Ahlswede and G. O. H. Katona, Contributions to the geometry of Hamming spaces, Discrete Math. 17 (1977), 1-22. MR 0465883 (57:5769)
  • [B1] A. Blokhuis, Few-distance sets, CWI Tract, vol. 7, Math. Centrum, Amsterdam, 1984. MR 751955 (87f:51023)
  • [C] H. Chernoff, A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations, Ann. Math. Statist. 23 (1952), 493-509. MR 0057518 (15:241c)
  • [D] P. Delsarte, On the four principal parameters of a code, J. Inform. Control 23 (1973), 407-438. MR 0335135 (48:13453)
  • [DP] P. Delsarte and P. Piret, An extension of an inequality by Ahlswede, El Gamal and Pang for pairs of binary codes, Discrete Math. 55 (1985), 313-315. MR 802670 (86j:94055)
  • [DF] M. Deza and P. Frankl, The Erdös Ko-Rado theorem 22 years later, SIAM J. Algebraic Discrete Methods 4 (1983), 419-431. MR 721612 (86a:05004)
  • [EFIN] H. Enomoto, P. Frankl, N. Ito and K. Nomura, Codes with given distances, Graphs Combin. (to appear). MR 932110 (89a:94015)
  • [EKR] P. Erdös, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. 12 (1961), 313-320. MR 0140419 (25:3839)
  • [E1] P. Erdös, Problems and results in graph theory and combinatorial analysis, Proc. Fifth British Comb. Conf. 1975 Aberdeen, Congressus Numerantium, 15-Utilitas Math., Winnipeg, 1976. MR 0409246 (53:13006)
  • [E2] -, The combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25-42. MR 602413 (82k:05001)
  • [EGMRSS] P. Erdös, R. L. Graham, P. Montgomery, B. L. Rothschild, J. H. Spencer and E. G. Straus, Euclidean Ramsey theorems, J. Combin. Theory Ser. A 14 (1973), 341-363. MR 0316277 (47:4825)
  • [ES] P. Erdös, and E. Szemerédi, Combinatorial properties of systems of sets, J. Combin. Theory Ser. A 24 (1978), 303-313. MR 0491202 (58:10467)
  • [F1] P. Frankl, The Erdös-Ko-Rado theorem is true for $ n = ckt$, Proc. Fifth Hungar. Combin. Colloq., North-Holland, Amsterdam, 1978, pp. 365-375. MR 519277 (80c:05014)
  • [F2] -, Bounding the size of a family knowing the differences, Acta Math. Acad. Sci. Hungar. 19 (1984).
  • [F3] -, Orthogonal vectors and codes with missing distances, Combinatorica 6 (1986).
  • [F4] -, Generalizations of theorems of Katona and Milner, Acta Math. Hungar. 27 (1976), 353-363. MR 0414370 (54:2473)
  • [FF1] P. Frankl and Z. Füredi, On hypergraphs without two edges intersecting in a given number of vertices, J. Combin. Theory Ser. A 36 (1984), 230-236. MR 734980 (86a:05091)
  • [FF2] -, Forbidding just one intersection, J. Combin. Theory Ser. A 39 (1985), 160-176. MR 793269 (86j:05008)
  • [FR] P. Frankl and V. Rödl, All triangles are Ramsey, Trans. Amer. Math. Soc. 292 (1986), 277-279. MR 854099 (88d:05018)
  • [FW] P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357-368. MR 647986 (84g:05085)
  • [H] L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory 1 (1966), 385-393. MR 0200192 (34:91)
  • [I] N. Ito, Hadamard graphs. I, Graphs Combin. 1 (1985), 57-64. MR 796183 (87b:05094)
  • [K] G. O. H. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964), 329-337. MR 0168468 (29:5731)
  • [LR] D. G. Larman and C. A. Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972), 1-24. MR 0319055 (47:7601)
  • [O] A. M. Odlyzko, On the ranks of some $ (0,1)$-matrices with constant row sums, J. Austral. Math. Soc. Ser. A 31 (1981), 193-201. MR 629173 (82j:05032)
  • [P] C. L. M. van Pul, Constant distance code pairs, Nederl. Akad. Wetensch. Proc. (to appear).
  • [Ry] H. J. Ryser, An extension of a theorem of de Bruijn and Erdös on combinatorial designs, J. Algebra 10 (1968), 246-261. MR 0229529 (37:5103)
  • [R] V. Rödl, On a packing and covering problem, European J. Combin. 6 (1985), 69-78. MR 793489 (86k:05033)
  • [W] R. M. Wilson, The exact bound in the Erdös-Ko-Rado theorem, Combinatorica 4 (1984), 247-260. MR 771733 (86f:05007)

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

DOI: https://doi.org/10.1090/S0002-9947-1987-0871675-6
Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society