Title:  Combinatorial remedies 
Author:  Mackey, John Fletcher 
Date:  1994 
Abstract:  This dissertation consists of 3 chapters which consider distinct combinatorial problems. In the first chapter we consider objects known as groupies. A nonisolated 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 picycles 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 nvertex 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. 
Description:  Thesis (Ph. D.)University of Hawaii at Manoa, 1994.
Includes bibliographical references (leaves 2930) Microfiche. 30 leaves, bound ill. 29 cm 
URI:  http://hdl.handle.net/10125/9962 
Rights:  All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner. 
Description  Files  Size  Format  View 

Restricted for viewing only  uhm_phd_9429633_r.pdf  781.9Kb 
View/ 

For UH users only  uhm_phd_9429633_uh.pdf  769.3Kb 
View/ 