Some extremal problems on gamma-graphs

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

Preview

Text 1973-25.pdf Download (931kB) | Preview

Abstract

Let f(r)(n;k,s) denote the smallest t for which every r-graph with n vertices and t r-tuples contains a subgraph with k vertices and at least s r-tuples. 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 r-graph 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.

Actions (login required)

Edit Item