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

Show simple item record

Item Description Mackey, John Fletcher en_US 2009-07-15T17:59:26Z 2009-07-15T17:59:26Z 1994 en_US
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

This item appears in the following Collection(s)

Show simple item record


Advanced Search


My Account