Abstract
In this paper we prove that ifℱ is a family ofk-subsets of ann-set, μ0, μ1, ..., μs are distinct residues modp (p is a prime) such thatk ≡ μ0 (modp) and forF ≠ F′ ≠ℱ we have |F ∩F′| ≡ μi (modp) for somei, 1 ≦i≦s, then |ℱ|≦( n s ).
As a consequence we show that ifR n is covered bym sets withm<(1+o(1)) (1.2)n then there is one set within which all the distances are realised.
It is left open whether the same conclusion holds for compositep.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
L. Babai andP. Frankl, On set intersections,J. Comb. Th. A28 (1980), 103–105.
M. Deza, P. Erdős andP. Frankl, Intersection properties of systems of finite sets,Proc. London Math. Soc.36 (1978), 369–384.
M. Deza, P. Erdős andN. M. Singhi, Combinatorial problems on subsets and their intersections,Advances in Mathematics, Suppl. Studies1 (1978), 259–265.
M. Deza andI. G. Rosenberg, Cardinalités, de sommets et d’arêtes d’hypergraphes satisfaisant à certaines conditions d’intersection,Cahlers CERO.20 (1978), 279–285.
P. Erdős, Problems and results in graph theory and combinatorial analysis,Proc. Fifth British Comb. Conf. 1975 Aberdeen, Congressus Numerantium,15 — Utilitas Mathematica, Winnipeg, 1976.
P. Erdős, Some remarks on the theory of graphs,Bull. Amer. Math. Soc.53 (1947), 292–294.
P. Erdős, Problems and results in chromatic graph theory, in:Proof techniques in graph theory (F. Harary ed.), Academic Press, London, 1969, 27–35.
P. Frankl, Extremal problems and coverings of the space,European J. Combs,1 (1980), 101–106.
P. Frankl, A constructive lower bound for Ramsey numbers,Ars Comb.3 (1977), 297–302.
P. Frankl, Problem session,Proc. French—Canadian Joint Comb. Coll., Montreal 1978.
P. Frankl, Families of finite sets with prescribed cardinalities for pairwise intersections,Acta Math. Acad. Sci. Hung., to appear.
P. Frankl andI. G. Rosenberg, An intersection problem for finite sets, Europ. J. Comb2 (1981).
H. Hadwiger, Überdeckungssätze für den Euklidischen Raum,Portugaliae Math.4 (1944), 140–144.
H. Hadwiger, Überdeckung des Euklidischen Raumes durch kongruente Mengen,Portugaliae Math.4 (1945), 238–242.
D. G. Larman, A note on the realization of distances within sets in euclidean space,Comment. Math. Helvet.53 (1978), 529–535.
D. G. Larman andC. A. Rogers, The realization of distances within sets in euclidean space,Mathematika19 (1972), 1–24.
D. E. Raiskii, The realization of all distances in a decomposition ofRn inton + 1 parts (Russian)Mat. Zametki7 (1970), 319–323.
D. K. Ray-Chaudhuri andR. M. Wilson, Ont-designs,Osaka J. Math.12 (1975), 735–744.
H. J. Ryser, An extension of a theorem of de Bruijn and Erdõs on combinatorial designs,J. Algebra10 (1968), 246–261.