Simonovits, Miklós and T. Sós, Vera (1980) Intersection theorems on structures. ANNALS OF DISCRETE MATHEMATICS, 6. pp. 301313. ISSN 01675060

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, NorthHolland, 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.
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:54 
Last Modified:  25 Jun 2020 14:54 
URI:  http://real.mtak.hu/id/eprint/110466 
Actions (login required)
Edit Item 