Counting Triangles in Some Ramsey Graphs
by
Andrew Lin
Golisano College of Computing and Information Sciences, Rochester Institute of Technology
Coauthors: John Mackey, Department of Mathematical Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA

In graph theory, the Ramsey number R(H₁, H₂) for simple graphs H₁ and H₂, is the smallest positive integer n such that for all graphs G of n vertices, either H₁ is a subgraph of G or H₂ is a subgraph of the complement of G.

A well known result by Goodman states that the number of monochromatic triangles in a 2-coloring of the edges of a complete graph is determined by the degrees of its vertices. We extend this result to the case of bounding the number of triangles in the first color. We also apply it to derive the upper bounds on some non-diagonal Ramsey numbers, and in particular we show that R(K₄-e, K₈) ≤ 45. This technique can potentially prove useful in cases of Ramsey numbers involving book graphs B_k.

Date received: April 10, 2009