Combinatorial remedies

Abstract

This dissertation consists of 3 chapters which consider distinct combinatorial problems. In the first chapter we consider objects known as groupies. A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. It is well known that every graph must contain at least one groupie. The graph Kn - e contains precisely 2 groupie vertices for n ≥2. In this chapter we derive a lower bound for the number of groupies in terms of the number of vertices of each particular degree. This shows, in particular, that any graph with 2 or more vertices must contain at least 2 groupies. In chapter 2 we show that, for a prime number p+n+1 , the number of pth powers in Sn+1 is n+1 times the number of pth powers in Sn. Here Sn denotes the symmetric group on n objects. Our technique also yields a recursion for calculating the number of r": powers in Sn+1. An analogous identity, and corresponding recursion, for pth powers containing a specified number of pi-cycles is also obtained. This generalizes work of Blum in the case p = 2, and Chernoff's work for general p. Finally, in chapter 3, we use techniques introduced by Giraud to obtain lower bounds for certain Ramsey Numbers. The Ramsey Number R(k,j) is defined to be the least positive integer n such that every n-vertex graph contains either a clique of order k or an independent set of order j. In particular we show that R (6, 6) ≤ 165, R (7, 7) ≤ 540, R (8, 8) ≤ 1870, R (9, 9) ≤ 6625, and R (10, 10) ≤ 23854 . These estimates replace bounds of 166, 574, 1982, 7042, and 25082, respectively.