| Staton introduced the notion of Ramsey-type numbers in his 1977 dissertation. He defined the Ramsey-type number RD ( m, n) to be the smallest integer for which, any graph of order RD (m, n) and maximum degree at most D, must, contain a clique of size m or an independent set of size n. Independence ratios, which are define by mu( G) = aG nG , play an important role in this theory. If we let GD (m) denote the class of Km-free graphs of maximum degree at most D, then a lower bound for the independence ratios of such graphs yields an upper bound for the Ramsey-type number RD (m, n). Lower bounds for independence ratios follow from size bounds of the form e (G) ≥ anu(G) + balpha(G).; This dissertation is concerned with the problem of calculating size and independence ratio bounds for various classes of graphs, and then using them to establish upper bounds for Ramsey-type numbers. Expressions that yield coefficients for multiple size bounds or multiple independence ratio bounds are of particular importance. For example, if we let m ≥ 3, and define am=2m-3and bm=-72m2 +32m-2, then, with one exception for the case m = 5, any connected G ∈ Gm (m) satisfies eG≥amn G+bma G. Given this size bound, we immediately obtain the independence ratio bound mG≥3 m-63m2-7m+4. These results are sharpened for members of G6 (6) and non-regular members of G7 (7).; An infinite class of size bounds that hold for all graphs is introduced and the set of independence ratios for which each is tight is established. The more difficult problem of defining tight size bounds for classes of graphs that satisfy a forbidden clique constraint, but no maximum degree constraint is also studied. These bounds are shown to be closely related to an independence ratio bound introduced by Fajtlowicz. |
