Brown, W. G. and Erdős, Pál and T. Sós, Vera (1973) Some extremal problems on gammagraphs. In: New Directions in the Theory of Graphs. Academic Press, Inc, New York (NY), pp. 5563.

Text
197325.pdf Download (931kB)  Preview 
Abstract
Let f(r)(n;k,s) denote the smallest t for which every rgraph with n vertices and t rtuples contains a subgraph with k vertices and at least s rtuples. It is proved that for integers k>r and s>1 there exists a positive constant ck,s such that f(r)(n;k,s)>ck,sn(rs−k)/(s−1). This inequality follows from a counting argument. Unfortunately a number of misprints make the proof seem incorrect. Inequality (1) ensures that there exists an rgraph H0(r) in M such that b(H0(r))<12m/(kr) (and not only m/(kr), as claimed on p. 60, 1.12). This, in turn, gives f(r)(n;k,s)≥12m, which is sufficient for the proof. The authors conjecture that limn→∞n−2f(3)(n;k,k−2) exists.
Item Type:  Book Section 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  25 Jun 2020 16:52 
Last Modified:  25 Jun 2020 16:52 
URI:  http://real.mtak.hu/id/eprint/110443 
Actions (login required)
Edit Item 