Date on Master's Thesis/Doctoral Dissertation

12-2011

Document Type

Doctoral Dissertation

Degree Name

Ph. D.

Department

Mathematics

Committee Chair

Kezdy, Andre

Subject

Number theory; Vector algebra

Abstract

A k-term quasi-progression of diameter d is a sequence {Xl,... ,xk} for which there exists a positive integer l such that l < Xi-Xi-1 < l+d, for all i = 2, ... ,k. Quasi-progressions may be thought of as arithmetic progressions with a certain amount of 'wiggle-room' allowed. Let Q(d, k) be the least positive integer such that every 2-coloring of {1, ... , Q(d, k)} contains a monochromatic k-term quasi-progression of diameter d. We prove a conjecture of Landman for certain values of k and d, provide counterexamples for some other cases, and determine that the conjecture always has the correct order of growth. Let A be the adjacency matrix of a non empty graph. Is there always a nonzero {0, 1}-vector in the row space of A that is not a row of A? Akbari, Cameron, and Khosrovshahi have shown that an affirmative answer to this question would imply bounds on many graph parameters as a function of the rank of the adjacency matrix. We demonstrate the existence of such vectors for certain families of graphs, examine techniques to find and verify the existence of such vectors, and show that if you generalize the problem to allow asymmetry in the matrices then some {0, 1 }-matrices do not have such vectors. In 1981, Andrew Yao asked "Should tables be sorted?". When the table has n cells that are filled with entries taken from a key space of m possibilities, he showed that it is possible to decide whether any member of the key space is present in the table by inspecting (querying) only one cell of the table if and only if m < 2n - 2. We make steps toward extending his result to the case where you are permitted two queries by considering several variations of the problem.

Download

Share

COinS