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

Preview

Text graham1980.pdf Download (234kB) | Preview

Abstract

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.''

Actions (login required)

Edit Item