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 is a family of subsets of without , , , then holds for some positive absolute constant . Here this conjecture is proved in a stronger form (Theorem 1.1), which solves a 250 problem of Erdös. Suppose is a code (i.e., a collection of sequences of length ) over an alphabet of elements, where is arbitrary. Suppose further that there are no two codewords at Hamming distance where is a fixed integer, , and is even if . Then , where depends only on and .

The following conjecture of Erdös and Szemerédi is also proved: If is a family of subsets of not containing a weak -system of size (cf. Definition 1.8), then , holds.

An old conjecture of Larman and Rogers is established in the following stronger form: Let be a collection of -dimensional -vectors, is a fixed integer. Suppose that does not contain pairwise orthogonal vectors. Then .

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 (cf. Theorem 9.1).

**[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*, 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*-*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)**

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