Forbidden intersections
Authors:
Peter Frankl and Vojtěch Rödl
Journal:
Trans. Amer. Math. Soc. 300 (1987), 259286
MSC:
Primary 05A05; Secondary 94B25
MathSciNet review:
871675
Fulltext 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]
Rudolf
Ahlswede, Abbas
El Gamal, and King
F. Pang, A twofamily extremal problem in Hamming space,
Discrete Math. 49 (1984), no. 1, 1–5. MR 737611
(86c:05005), http://dx.doi.org/10.1016/0012365X(84)901444
 [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
(57 #5769)
 [B1]
A.
Blokhuis, Fewdistance sets, CWI Tract, vol. 7, Stichting
Mathematisch Centrum Centrum voor Wiskunde en Informatica, Amsterdam, 1984.
MR 751955
(87f:51023)
 [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
(15,241c)
 [D]
Philippe
Delsarte, Four fundamental parameters of a code and their
combinatorial significance, Information and Control
23 (1973), 407–438. MR 0335135
(48 #13453)
 [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
(86j:94055), http://dx.doi.org/10.1016/S0012365X(85)80008X
 [DF]
M.
Deza and P.
Frankl, ErdősKoRado theorem—22 years later,
SIAM J. Algebraic Discrete Methods 4 (1983), no. 4,
419–431. MR
721612 (86a:05004), http://dx.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
(89a:94015), http://dx.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
(25 #3839)
 [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
(53 #13006)
 [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 (82k:05001), http://dx.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
(47 #4825)
 [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
(58 #10467)
 [F1]
P.
Frankl, The ErdősKoRado theorem is true for
𝑛=𝑐𝑘𝑡, Combinatorics (Proc. Fifth
Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János
Bolyai, vol. 18, NorthHolland, 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]
P.
Frankl, Generalizations of theorems of Katona and Milner, Acta
Math. Acad. Sci. Hungar. 27 (1976), no. 34,
359–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), no. 2, 230–236. MR 734980
(86a:05091), http://dx.doi.org/10.1016/00973165(84)900086
 [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
(86j:05008), http://dx.doi.org/10.1016/00973165(85)900354
 [FR]
Peter
Frankl and Vojtěch
Rödl, All triangles are Ramsey, Trans. Amer. Math. Soc. 297 (1986), no. 2, 777–779. MR 854099
(88d:05018), http://dx.doi.org/10.1090/S00029947198608540996
 [FW]
P.
Frankl and R.
M. Wilson, Intersection theorems with geometric consequences,
Combinatorica 1 (1981), no. 4, 357–368. MR 647986
(84g:05085), http://dx.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
(34 #91)
 [I]
Noboru
Ito, Hadamard graphs. I, Graphs Combin. 1
(1985), no. 1, 57–64. MR 796183
(87b:05094), http://dx.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
(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),
no. 2, 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]
Vojtěch
Rödl, On a packing and covering problem, European J.
Combin. 6 (1985), no. 1, 69–78. MR 793489
(86k:05033)
 [W]
Richard
M. Wilson, The exact bound in the ErdősKoRado
theorem, Combinatorica 4 (1984), no. 23,
247–257. MR
771733 (86f:05007), http://dx.doi.org/10.1007/BF02579226
 [A]
 N. Alon (personal communication).
 [AGP]
 R. Ahlswede, A. El Gamal and K. F. Pang, A twofamily extremal problem in Hamming space, Discrete Math. 49 (1984), 15. MR 737611 (86c:05005)
 [AK]
 R. Ahlswede and G. O. H. Katona, Contributions to the geometry of Hamming spaces, Discrete Math. 17 (1977), 122. MR 0465883 (57:5769)
 [B1]
 A. Blokhuis, Fewdistance 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), 493509. MR 0057518 (15:241c)
 [D]
 P. Delsarte, On the four principal parameters of a code, J. Inform. Control 23 (1973), 407438. 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), 313315. MR 802670 (86j:94055)
 [DF]
 M. Deza and P. Frankl, The Erdös KoRado theorem 22 years later, SIAM J. Algebraic Discrete Methods 4 (1983), 419431. 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), 313320. 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, 15Utilitas Math., Winnipeg, 1976. MR 0409246 (53:13006)
 [E2]
 , The combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 2542. 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), 341363. 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), 303313. MR 0491202 (58:10467)
 [F1]
 P. Frankl, The ErdösKoRado theorem is true for , Proc. Fifth Hungar. Combin. Colloq., NorthHolland, Amsterdam, 1978, pp. 365375. 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), 353363. 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), 230236. MR 734980 (86a:05091)
 [FF2]
 , Forbidding just one intersection, J. Combin. Theory Ser. A 39 (1985), 160176. MR 793269 (86j:05008)
 [FR]
 P. Frankl and V. Rödl, All triangles are Ramsey, Trans. Amer. Math. Soc. 292 (1986), 277279. MR 854099 (88d:05018)
 [FW]
 P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357368. MR 647986 (84g:05085)
 [H]
 L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory 1 (1966), 385393. MR 0200192 (34:91)
 [I]
 N. Ito, Hadamard graphs. I, Graphs Combin. 1 (1985), 5764. MR 796183 (87b:05094)
 [K]
 G. O. H. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964), 329337. MR 0168468 (29:5731)
 [LR]
 D. G. Larman and C. A. Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972), 124. 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), 193201. 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), 246261. MR 0229529 (37:5103)
 [R]
 V. Rödl, On a packing and covering problem, European J. Combin. 6 (1985), 6978. MR 793489 (86k:05033)
 [W]
 R. M. Wilson, The exact bound in the ErdösKoRado theorem, Combinatorica 4 (1984), 247260. 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:
http://dx.doi.org/10.1090/S00029947198708716756
PII:
S 00029947(1987)08716756
Article copyright:
© Copyright 1987 American Mathematical Society
