The topic of this thesis is the hat problem. In this problem, a team of n players enters a room, and a blue or red hat is randomly placed on the head of each player. Every player can see the hats of all of the other players but not his own. Then each player must simultaneously guess the color of his own hat or pass. The team wins if at least one player guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of winning. This thesis is based on publications, which form the second chapter. In the first chapter we give an overview of the published results. In Section 1.1 we introduce to the hat problem and the hat problem on a graph, where vertices correspond to players, and a player can see the adjacent players. To the hat problem on a graph we devote the next few sections. First, we give some fundamental theorems about the problem. Then we solve the hat problem on trees, cycles, and unicyclic graphs. Next we consider the hat problem on graphs with a universal vertex. We also investigate the problem on graphs with a neighborhood-dominated vertex. In addition, we consider the hat problem on disconnected graphs. Next we investigate the problem on graphs such that the only known information are degrees of vertices. We also present Nordhaus-Gaddum type inequalities for the hat problem on a graph. In Section 1.6 we investigate the hat problem on directed graphs. The topic of Section 1.7 is the generalized hat problem with q >= 2 colors. A modified hat problem is considered in Section 1.8. In this problem there are n >= 3 players and two colors. The players do not have to guess their hat colors simultaneously and we modify the way of making a guess. We give an optimal strategy for this problem which guarantees the win. Applications of the hat problem and its connections to different areas of science are presented in Section 1.9. We also give there a comprehensive list of variations of the hat problem considered in the literature.

The graceful tree conjecture was first introduced over 50 years ago, and to this day it remains largely unresolved. Ideas for how to label arbitrary trees have been sparse, and so most work in this area focuses on demonstrating that particular classes of trees are graceful. In my research, I continue this effort and establish the gracefulness of some new tree types using previously developed techniques for constructing graceful trees. Meanwhile, little work has been done on developing computational methods for obtaining graceful labelings, as direct approaches are computationally infeasible for even moderately large trees. With this in mind, I have designed a new computational approach for constructing a graceful labeling for trees with sufficiently many leaves. This approach leverages information about the local structures present in a given tree in order to construct a suitable labeling. It has been shown to work for many small cases and thoughts on how to extend this approach for larger trees are put forth. / McAnulty College and Graduate School of Liberal Arts; / Computational Mathematics / MS; / Thesis;

The independence number alpha of a graph is the size of a maximum independent set of vertices. An independent set is a set of vertices where every pair of vertices in non-adjacent. This number is known to be hard to compute. The bound we worked with is defined as epsilon = max[e(v)-eh(v)] over all the vertices in the vertex set, V(G). e(v) is the number of vertices at even distance from v. eh(v) is the number of edges both of whose endpoints are at even distance from v. Epsilon can be calculated in polynomial time. Siemion Fajtlowicz proved that alpha is greater than or equal to epsilon for any graph. We worked to characterize graphs where alpha=epsilon.

A tree decomposition is a tool which allows for analysis of the underlying tree structure of graphs which are not trees. Given a class of graphs with bounded tree width, many NP-complete problems can be computed in linear time for graphs in the class. Clique width of a graph G is a measure of the number of labels required to construct G using several particular graph operations. For any integer k, both the class of graphs with tree width at most k and the class of graphs with clique width at most k have a decidable monadic second order theory. In this paper we explore some recent results in applying these graph measures and their relation to monadic second order logic.

The combinatorial objects known as association schemes arise in group theory, extremal graph theory, coding theory, the design of experiments, and even quantum information theory. One may think of a d-class association scheme as a (d + 1)-dimensional matrix algebra over R closed under entrywise products. In this context, an imprimitive scheme is one which admits a subalgebra of block matrices, also closed under the entrywise product. Such systems of imprimitivity provide us with quotient schemes, smaller association schemes which are often easier to understand, providing useful information about the structure of the larger scheme. One important property of any association scheme is that we may find a basis of d + 1 idempotent matrices for our algebra. A cometric scheme is one whose idempotent basis may be ordered E0, E1, . . . , Ed so that there exists polynomials f0, f1, . . . , fd with fi ◦ (E1) = Ei and deg(fi) = i for each i. Imprimitive cometric schemes relate closely to t-distance sets, sets of unit vectors with only t distinct angles, such as equiangular lines and mutually unbiased bases. Throughout this thesis we are primarily interested in three distinct goals: building new examples of cometric association schemes, drawing connections between cometric association schemes and other objects either combinatorial or geometric, and finding new realizability conditions on feasible parameter sets — using these conditions to rule out open parameter sets when possible. After introducing association schemes with relevant terminology and definitions, this thesis focuses on a few recent results regarding cometric schemes with small d. We begin by examining the matrix algebra of any such scheme, first looking for low rank positive semidefinite matrices with few distinct entries and later establishing new conditions on realizable parameter sets. We then focus on certain imprimitive examples of both 3- and 4-class cometric association schemes, generating new examples of the former while building realizability conditions for both. In each case, we examine the related t-distance sets, giving conditions which work towards equivalence; in the case of 3-class Q-antipodal schemes, an equivalence is established. We conclude by partially extending a result of Brouwer and Koolen concerning the connectivity of graphs arising from metric association schemes.

Property testing, especially that of geometric and graph properties, is an ongoing area of research. In this thesis, we present a result from each of the two areas. For the problem of convexity testing in high dimensions, we give nearly matching upper and lower bounds for the sample complexity of algorithms have one-sided and two-sided error, where algorithms only have access to labeled samples independently drawn from the standard multivariate Gaussian. In the realm of graph property testing, we give an improved lower bound for testing acyclicity in directed graphs of bounded degree. Central to the area of topological graph theory is the genus parameter, but the complexity of determining the genus of a graph is poorly understood when graphs become nearly complete. We summarize recent progress in understanding the space of minimum genus embeddings of such dense graphs. In particular, we classify all possible face distributions realizable by minimum genus embeddings of complete graphs, present new constructions for genus embeddings of the complete graphs, and find unified constructions for minimum triangulations of surfaces.

Learning on graphs has been studied for decades with abundant models proposed, yet many of their behaviors and relations remain unclear. This thesis fills this gap by introducing a novel second-order Markov chain, called partially absorbing random walks (ParWalk). Different from ordinary random walk, ParWalk is absorbed at the current state $i$ with probability $p_i$, and follows a random edge out with probability $1-p_i$. The partial absorption results in absorption probability between any two vertices, which turns out to encompass various popular models including PageRank, hitting times, label propagation, and regularized Laplacian kernels. The unified treatment reveals the distinguishing characteristics of these models arising from different contexts, and allows comparing them and transferring findings from one paradigm to another. The key for learning on graphs is capitalizing on the cluster structure of the underlying graph. The absorption probabilities of ParWalk, turn out to be highly effective in capturing the cluster structure. Given a query vertex $q$ in a cluster $\mathcal{S}$, we show that when the absorbing capacity ($p_i$) of each vertex on the graph is small, the probabilities of ParWalk to be absorbed at $q$ have small variations in region of high conductance (within clusters), but have large gaps in region of low conductance (between clusters). And the less absorbent the vertices of $\mathcal{S}$ are, the better the absorption probabilities can represent the local cluster $\mathcal{S}$. Our theory induces principles for designing reliable similarity measures and provides justification to a number of popular ones such as hitting times and the pseudo-inverse of graph Laplacian. Furthermore, it reveals their new important properties. For example, we are the first to show that hitting times is better in retrieving sparse clusters, while the pseudo-inverse of graph Laplacian is better for dense ones. The theoretical insights instilled from ParWalk guide us in developing robust algorithms for various applications including local clustering, semi-supervised learning, and ranking. For local clustering, we propose a new method for salient object segmentation. By taking a noisy saliency map as the probability distribution of query vertices, we compute the absorption probabilities of ParWalk to the queries, producing a high-quality refined saliency map where the objects can be easily segmented. For semi-supervised learning, we propose a new algorithm for label propagation. The algorithm is justified by our theoretical analysis and guaranteed to be superior than many existing ones. For ranking, we design a new similarity measure using ParWalk, which combines the strengths of both hitting times and the pseudo-inverse of graph Laplacian. The hybrid similarity measure can well adapt to complex data of diverse density, thus performs superiorly overall. For all these learning tasks, our methods achieve substantial improvements over the state-of-the-art on extensive benchmark datasets.

No description available.

Chan, Ying Ying. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 66-69). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.6 / Chapter 1.1 --- Weierstrass function --- p.7 / Chapter 1.2 --- Rademacher series --- p.10 / Chapter 2 --- Preliminaries --- p.12 / Chapter 2.1 --- Hausdorff dimension and box dimension .. --- p.12 / Chapter 2.2 --- Properties of Hausdorff dimension and box dimension --- p.15 / Chapter 2.3 --- Basic techniques in computing dimensions . --- p.16 / Chapter 2.4 --- Graphs of functions --- p.18 / Chapter 3 --- Weierstrass Function --- p.20 / Chapter 3.1 --- Weierstrass-like functions and their box dimension --- p.20 / Chapter 3.2 --- Hausdorff dimension of Weierstrass-like graphs --- p.23 / Chapter 3.3 --- Weierstrass function with a random phase angle --- p.31 / Chapter 4 --- Rademacher series --- p.37 / Chapter 4.1 --- Basic properties --- p.38 / Chapter 4.2 --- Box dimension for Rademacher series with generalization --- p.39 / Chapter 4.3 --- Some remainders on the infinite Bernoulli convolution --- p.46 / Chapter 5 --- Rademacher series with Pisot reciprocal as parameter --- p.48 / Chapter 5.1 --- Pisot number --- p.48 / Chapter 5.2 --- Hausdorff dimension --- p.49 / Chapter 5.3 --- Matrix representation --- p.54 / Chapter 5.3.1 --- Set-up --- p.54 / Chapter 5.3.2 --- Case of golden ratio --- p.61

No description available.