A note on the intersection properties of subsets of integers

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. 106-110. ISSN 0097-3165


Download (234kB) | Preview


From the introduction: "According to the de Bruijn-Erdős theorem, if A1,⋯,AN are subsets of an n-element 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 number-theoretic type.''

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 25 Jun 2020 14:58
Last Modified: 25 Jun 2020 14:58

Actions (login required)

Edit Item Edit Item