Intersection theorems on structures

Simonovits, Miklós and T. Sós, Vera (1980) Intersection theorems on structures. ANNALS OF DISCRETE MATHEMATICS, 6. pp. 301-313. ISSN 0167-5060

Preview

Text simonovits1980.pdf Download (738kB) | Preview

Abstract

All the graphs considered are simple, i.e., without loops or multiple edges. The intersection of two graphs is just the graph formed by the edges common to both of them. Let K be a family of graphs and n a positive integer. Then f(n,K) denotes the maximum number of distinct (labeled) graphs on n vertices such that the interesection of any two is in K. The authors first investigated this function in a previous paper [Combinatorics, II (Keszthely, 1976), pp. 1017–1030, North-Holland, Amsterdam, 1978; MR0519324 (80i:05062b)]. In particular, they proved that if K consists of all the subdivisions of K for given finite graphs, then f(n,K) is polynomially bounded. The present paper reviews the main results and reports on further progress, but contains no proofs. Let us mention a very recent open problem, due to the second author: Let T be the class of all graphs which contain a triangle. Prove or disprove f(n,T)=2(n2)−3. Apart from graphs, the authors consider intervals and arithmetic progressions. Those problems were introduced by R. L. Graham and the authors [J. Combin. Theory Ser. A 28 (1980), no. 1, 106–110]. Among other results, they have proved that one cannot do better than taking all the subsets of size ≤3 of the integers {1,⋯,n}, if the pairwise intersections have to be arithmetic progressions. The authors prove that if the intersection has to be an arithmetic progression of length at least k, k≥2, then the optimal bound is (π2/24+o(1))n2. The case k=1 is still open.

Actions (login required)

Edit Item