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

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]**Rudolf Ahlswede, Abbas El Gamal, and King F. Pang,*A two-family extremal problem in Hamming space*, Discrete Math.**49**(1984), no. 1, 1–5. MR**737611**, https://doi.org/10.1016/0012-365X(84)90144-4**[AK]**R. Ahlswede and G. O. H. Katona,*Contributions to the geometry of Hamming spaces*, Discrete Math.**17**(1977), no. 1, 1–22. MR**0465883**, https://doi.org/10.1016/0012-365X(77)90017-6**[B1]**A. Blokhuis,*Few-distance sets*, CWI Tract, vol. 7, Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1984. MR**751955****[C]**Herman Chernoff,*A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations*, Ann. Math. Statistics**23**(1952), 493–507. MR**0057518****[D]**Philippe Delsarte,*Four fundamental parameters of a code and their combinatorial significance*, Information and Control**23**(1973), 407–438. MR**0335135****[DP]**Ph. Delsarte and Ph. Piret,*An extension of an inequality by Ahlswede, El Gamal and Pang for pairs of binary codes*, Discrete Math.**55**(1985), no. 3, 313–315. MR**802670**, https://doi.org/10.1016/S0012-365X(85)80008-X**[DF]**M. Deza and P. Frankl,*Erdős-Ko-Rado theorem—22 years later*, SIAM J. Algebraic Discrete Methods**4**(1983), no. 4, 419–431. MR**721612**, https://doi.org/10.1137/0604042**[EFIN]**H. Enomoto, P. Frankl, N. Ito, and K. Nomura,*Codes with given distances*, Graphs Combin.**3**(1987), no. 1, 25–38. MR**932110**, https://doi.org/10.1007/BF01788526**[EKR]**P. Erdős, Chao Ko, and R. Rado,*Intersection theorems for systems of finite sets*, Quart. J. Math. Oxford Ser. (2)**12**(1961), 313–320. MR**0140419**, https://doi.org/10.1093/qmath/12.1.313**[E1]**P. Erdős,*Problems and results in graph theory and combinatorial analysis*, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Utilitas Math., Winnipeg, Man., 1976, pp. 169–192. Congressus Numerantium, No. XV. MR**0409246****[E2]**P. Erdős,*On the combinatorial problems which I would most like to see solved*, Combinatorica**1**(1981), no. 1, 25–42. MR**602413**, https://doi.org/10.1007/BF02579174**[EGMRSS]**P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, and E. G. Straus,*Euclidean Ramsey theorems. I*, J. Combinatorial Theory Ser. A**14**(1973), 341–363. MR**0316277****[ES]**P. Erdős and E. Szemerédi,*Combinatorial properties of systems of sets*, J. Combinatorial Theory Ser. A**24**(1978), no. 3, 308–313. MR**0491202****[F1]**P. Frankl,*The Erdős-Ko-Rado theorem is true for 𝑛=𝑐𝑘𝑡*, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 365–375. MR**519277****[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]**P. Frankl,*Generalizations of theorems of Katona and Milner*, Acta Math. Acad. Sci. Hungar.**27**(1976), no. 3-4, 359–363. MR**0414370**, https://doi.org/10.1007/BF01902114**[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), no. 2, 230–236. MR**734980**, https://doi.org/10.1016/0097-3165(84)90008-6**[FF2]**Peter Frankl and Zoltán Füredi,*Forbidding just one intersection*, J. Combin. Theory Ser. A**39**(1985), no. 2, 160–176. MR**793269**, https://doi.org/10.1016/0097-3165(85)90035-4**[FR]**Peter Frankl and Vojtěch Rödl,*All triangles are Ramsey*, Trans. Amer. Math. Soc.**297**(1986), no. 2, 777–779. MR**854099**, https://doi.org/10.1090/S0002-9947-1986-0854099-6**[FW]**P. Frankl and R. M. Wilson,*Intersection theorems with geometric consequences*, Combinatorica**1**(1981), no. 4, 357–368. MR**647986**, https://doi.org/10.1007/BF02579457**[H]**L. H. Harper,*Optimal numberings and isoperimetric problems on graphs*, J. Combinatorial Theory**1**(1966), 385–393. MR**0200192****[I]**Noboru Ito,*Hadamard graphs. I*, Graphs Combin.**1**(1985), no. 1, 57–64. MR**796183**, https://doi.org/10.1007/BF02582929**[K]**Gy. Katona,*Intersection theorems for systems of finite sets*, Acta Math. Acad. Sci. Hungar**15**(1964), 329–337. MR**0168468**, https://doi.org/10.1007/BF01897141**[LR]**D. G. Larman and C. A. Rogers,*The realization of distances within sets in Euclidean space*, Mathematika**19**(1972), 1–24. MR**0319055**, https://doi.org/10.1112/S0025579300004903**[O]**A. M. Odlyzko,*On the ranks of some (0,1)-matrices with constant row sums*, J. Austral. Math. Soc. Ser. A**31**(1981), no. 2, 193–201. MR**629173****[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**, https://doi.org/10.1016/0021-8693(68)90099-9**[R]**Vojtěch Rödl,*On a packing and covering problem*, European J. Combin.**6**(1985), no. 1, 69–78. MR**793489**, https://doi.org/10.1016/S0195-6698(85)80023-8**[W]**Richard M. Wilson,*The exact bound in the Erdős-Ko-Rado theorem*, Combinatorica**4**(1984), no. 2-3, 247–257. MR**771733**, https://doi.org/10.1007/BF02579226

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