Graham, R. L. and Simonovits, Miklós and T. Sós, Vera (1980) A note on the intersection properties of subsets of integers. JOURNAL OF COMBINATORIAL THEORY SERIES A, 28 (1). pp. 106110. ISSN 00973165

Text
graham1980.pdf Download (234kB)  Preview 
Abstract
From the introduction: "According to the de BruijnErdős theorem, if A1,⋯,AN are subsets of an nelement set S and Ai∩Aj=1 for i≠j (where X denotes the cardinality of X), then N≤n. This result is sharp, e.g., if S={1,⋯,n}=[1,n] and A1={1,n}, A2={2,n},⋯,An−1={n−1,n}, and An={1,2,⋯,n−1}, then Ai∩Aj=1 for 1≤i<j≤n. Many similar theorems have been proved for sets. One could also ask what analogous results can be proved if the Ai have some extra structure and the condition on the intersection also refers to this structure. For example, it has been proved [Simonovits and Sós, Problèmes combinatoires et théorie des graphes (Orsay, 1976), pp. 389–391, CNRS, Paris, 1980: MR0540021 (80i:05062a)], that if A1,⋯,AN are graphs on the same n vertices and the intersection of two graphs Ai and Aj is defined as the graph without isolated vertices whose edges are the common edges of Ai and Aj, then the condition `Ai∩Aj is a (nonempty) cycle for 1≤i<j≤N' implies that N≤(n2)−2, which is again sharp. Here we investigate the case in which A1,⋯,AN is a system of subsets of {1,⋯,n} and the intersection condition is of a numbertheoretic type.''
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  25 Jun 2020 14:58 
Last Modified:  25 Jun 2020 14:58 
URI:  http://real.mtak.hu/id/eprint/110467 
Actions (login required)
Edit Item 