ScholarSpace will be brought offline for upgrades on Wednesday December 9th at 11AM HST. Service will be disrupted for approximately 2 hours. Please direct any questions to sspace@hawaii.edu

﻿

## Item Description

 dc.contributor.author Mackey, John Fletcher en_US dc.date.accessioned 2009-07-15T17:59:26Z dc.date.available 2009-07-15T17:59:26Z dc.date.issued 1994 en_US dc.identifier.uri http://hdl.handle.net/10125/9962 dc.description Thesis (Ph. D.)--University of Hawaii at Manoa, 1994. en_US dc.description Includes bibliographical references (leaves 29-30) en_US dc.description Microfiche. en_US dc.description 30 leaves, bound ill. 29 cm en_US dc.description.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. en_US dc.language.iso en-US en_US dc.relation Theses for the degree of Doctor of Philosophy (University of Hawaii at Manoa). Mathematics; no. 3007 en_US dc.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. en_US dc.title Combinatorial remedies en_US dc.type Thesis en_US dc.type.dcmi Text en_US

## Item File(s)

Description Files Size Format View
Restricted for viewing only uhm_phd_9429633_r.pdf 781.9Kb PDF View/Open
For UH users only uhm_phd_9429633_uh.pdf 769.3Kb PDF View/Open