Bibliography: pages 192-195 / The avoidability, or unavoidability of patterns in words over finite alphabets has been studied extensively. The word α over a finite set A is said to be unavoidable for an infinite set B+ of nonempty words over a finite set B if, for all but finitely many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that φ(α) is a factor of w. In this treatise, we start by presenting a historical background of results that are related to unavoidability. We present and discuss the most important theorems surrounding unavoidability in detail. We present various complexity-related properties of unavoidable words. For words that are unavoidable, we provide a constructive upper bound to the lengths of words that avoid them. In particular, for a pattern α of length n over an alphabet of size r, we give a concrete function N(n, r) such that no word of length N(n, r) over the alphabet of size r avoids α. A natural subsequent question is how many unavoidable words there are. We show that the fraction of words that are unavoidable drops exponentially fast in the length of the word. This allows us to calculate an upper bound on the number of unavoidable patterns for any given finite alphabet. Subsequently, we investigate computational aspects of unavoidable words. In particular, we exhibit concrete algorithms for determining whether a word is unavoidable. We also prove results on the computational complexity of the problem of determining whether a given word is unavoidable. Specifically, the NP-completeness of the aforementioned problem is established. / Decision Sciences / D. Phil. (Operations Research)

In der Ramsey Theorie fuer Graphen haben Burr und Erdos vor nunmehr fast dreissig Jahren zwei Vermutungen formuliert, die sich als richtungsweisend erwiesen haben. Es geht darum diejenigen Graphen zu charakterisieren, deren Ramsey Zahlen linear in der Anzahl der Knoten wachsen. Diese Vermutungen besagen, dass Ramsey Zahlen linear fuer alle degenerierten Graphen wachsen und dass die Ramsey Zahlen von Wuerfeln linear wachsen. Ein Ziel dieser Dissertation ist es, abgeschwaechte Varianten dieser Vermutungen zu beweisen. In der topologischen Ramseytheorie bewies Kojman vor kurzem eine topologische Umkehrung des Satzes von Hindman und fuehrte gleichzeitig sogenannte Hindman-Raeume und van der Waerden-Raeume ein (beide sind eine Teilmenge der folgenkompakten Raeume), die jeweils zum Satz von Hindman beziehungsweise zum Satz von van der Waerden korrespondieren. In der Dissertation wird zum einen eine Verstaerkung der Umkehrung des Satzes von van der Waerden bewiesen. Weiterhin wird der Begriff der Differentialkompaktheit eingefuehrt, der sich in diesem Zusammenhang ergibt und der eng mit Hindman-Raeumen verknuepft ist. Dabei wird auch die Beziehung zwischen Differentialkompaktheit und anderen topologischen Raeumen untersucht. Im letzten Abschnitt des zweiten Teils werden kompakte dynamische Systeme verwendet, um ein klassisches Ramsey-Ergebnis von Brown und Hindman et al. ueber stueckweise syndetische Mengen ueber natuerlichen Zahlen und diskreten Halbgruppen auf lokal zusammenhaengende Halbgruppen zu verallgemeinern. / In graph Ramsey theory, Burr and Erdos in 1970s posed two conjectures which may be considered as initial steps toward the problem of characterizing the set of graphs for which Ramsey numbers grow linearly in their orders. One conjecture is that Ramsey numbers grow linearly for all degenerate graphs and the other is that Ramsey numbers grow linearly for cubes. Though unable to settle these two conjectures, we have contributed many weaker versions that support the likely truth of the first conjecture and obtained a polynomial upper bound for the Ramsey numbers of cubes that considerably improves all previous bounds and comes close to the linear bound in the second conjecture. In topological Ramsey theory, Kojman recently observed a topological converse of Hindman's theorem and then introduced the so-called Hindman space and van der Waerden space (both of which are stronger than sequentially compact spaces) corresponding respectively to Hindman's theorem and van der Waerden's theorem. In this thesis, we will strengthen the topological converse of Hindman's theorem by using canonical Ramsey theorem, and introduce differential compactness that arises naturally in this context and study its relations to other spaces as well. Also by using compact dynamical systems, we will extend a classical Ramsey type theorem of Brown and Hindman et al on piecewise syndetic sets from natural numbers and discrete semigroups to locally connected semigroups.

Let P = (p1, p2, . . . , pN ) be a sequence of points in the plane, where pi = (xi, yi) and x1 < x2 < · · · < xN . A famous 1935 Erdős-Szekeres theorem asserts that every such P contains a monotone subsequence S of √ N points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Ω(log N) points. First we define a (k + 1)-tuple K ⊆ P to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k + 1)-tuple. Then we say that S ⊆ P is kth-order monotone if its (k + 1)- tuples are all positive or all negative. In this thesis we investigate quantitative bound for the corresponding Ramsey-type result. We obtain an Ω(log(k−1) N) lower bound ((k − 1)-times iterated logarithm). We also improve bounds for related problems: Order types and One-sided sets of hyperplanes. 1

We investigate two combinatorial properties of classes of finite structures, as well as related applications to topological dynamics. Using the Hrushovski property of classes of finite structures -- a finite extension property of homomorphisms -- we can show the existence of ample generics. For example, Solecki proved the existence of ample generics in the context of finite metric spaces that do indeed possess this extension property. Furthermore, Kechris, Pestov and Todorcevic have shown that the Ramsey property of Fraisse classes of finite structures implies that the automorphism group of the corresponding Fraisse limit is extremely amenable, i.e., it possesses a very strong fixed point property. Gromov and Milman had shown that the unitary group of the infinite-dimensional separable Hilbert space is extremely amenable using non-combinatorial methods. This result encourages a deeper look into structural Euclidean Ramsey theory, i.e., Euclidean Ramsey theory in which we colour more than just points. In particular, we look at complete finite labeled graphs whose vertex sets are subsets of the Hilbert space and whose labels correspond to the inner products. We prove "Ramsey-type" and "Hrushovski-type" theorems for linearly ordered metric subspaces of "sufficiently" orthogonal sets. In particular, the latter is used to show a "Hrushovski version" of the Ramsey-type Matousek-Rodl theorem for simplices. It is known that the square root of the metric induced by the distance between vertices in graphs produces a metric space embeddable in a Euclidean space if and only if the graph is a metric subgraph of the Cartesian product of three types of graphs. These three are the half-cube graphs, the so-called cocktail party graphs, and the Gosset graph. We show that the class of metric spaces related to half-cube graphs -- metric spaces on sets with the symmetric difference metric -- satisfies the Hrushovski property up to 3 points, but not more. Moreover, the amalgamation in this class can be too restrictive to permit the Ramsey Property. Finally, following the work of Fouche, we compute the Ramsey degrees of structures induced by the leaf sets of boron trees. Also, we briefly show that this class does not satisfy the full Hrushovski property. Fouche's trees are in fact related to ultrametric spaces, as was observed by Lionel Nguyen van The. We augment Fouche's concept of orientation so that it applies to these boron tree structures. The upper bound computation of the Ramsey degree in this case, turns out to be an "asymmetric" version of the Graham-Rothschild theorem. Finally, we extend these structures to "oriented" ones, yielding a Ramsey class and a corresponding Fraisse limit whose automorphism group is extremely amenable.

We investigate two combinatorial properties of classes of finite structures, as well as related applications to topological dynamics. Using the Hrushovski property of classes of finite structures -- a finite extension property of homomorphisms -- we can show the existence of ample generics. For example, Solecki proved the existence of ample generics in the context of finite metric spaces that do indeed possess this extension property. Furthermore, Kechris, Pestov and Todorcevic have shown that the Ramsey property of Fraisse classes of finite structures implies that the automorphism group of the corresponding Fraisse limit is extremely amenable, i.e., it possesses a very strong fixed point property. Gromov and Milman had shown that the unitary group of the infinite-dimensional separable Hilbert space is extremely amenable using non-combinatorial methods. This result encourages a deeper look into structural Euclidean Ramsey theory, i.e., Euclidean Ramsey theory in which we colour more than just points. In particular, we look at complete finite labeled graphs whose vertex sets are subsets of the Hilbert space and whose labels correspond to the inner products. We prove "Ramsey-type" and "Hrushovski-type" theorems for linearly ordered metric subspaces of "sufficiently" orthogonal sets. In particular, the latter is used to show a "Hrushovski version" of the Ramsey-type Matousek-Rodl theorem for simplices. It is known that the square root of the metric induced by the distance between vertices in graphs produces a metric space embeddable in a Euclidean space if and only if the graph is a metric subgraph of the Cartesian product of three types of graphs. These three are the half-cube graphs, the so-called cocktail party graphs, and the Gosset graph. We show that the class of metric spaces related to half-cube graphs -- metric spaces on sets with the symmetric difference metric -- satisfies the Hrushovski property up to 3 points, but not more. Moreover, the amalgamation in this class can be too restrictive to permit the Ramsey Property. Finally, following the work of Fouche, we compute the Ramsey degrees of structures induced by the leaf sets of boron trees. Also, we briefly show that this class does not satisfy the full Hrushovski property. Fouche's trees are in fact related to ultrametric spaces, as was observed by Lionel Nguyen van The. We augment Fouche's concept of orientation so that it applies to these boron tree structures. The upper bound computation of the Ramsey degree in this case, turns out to be an "asymmetric" version of the Graham-Rothschild theorem. Finally, we extend these structures to "oriented" ones, yielding a Ramsey class and a corresponding Fraisse limit whose automorphism group is extremely amenable.

Title: Combinatorial Games Theory Author: Tomáš Valla Department / Institute: IUUK MFF UK Supervisor: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstract: In this thesis we study the complexity that appears when we consider the competitive version of a certain environment or process, using mainly the tools of al- gorithmic game theory, complexity theory, and others. For example, in the Internet environment, one cannot apply any classical graph algorithm on the graph of connected computers, because it usually requires existence of a central authority, that manipu- lates with the graph. We describe a local and distributed game, that in a competitive environment without a central authority simulates the computation of the weighted vertex cover, together with generalisation to hitting set and submodular weight func- tion. We prove that this game always has a Nash equilibrium and each equilibrium yields the same approximation of optimal cover, that is achieved by the best known ap- proximation algorithms. More precisely, the Price of Anarchy of our game is the same as the best known approximation ratio for this problem. All previous results in this field do not have the Price of Anarchy bounded by a constant. Moreover, we include the results in two more fields, related to the complexity of competitive...

The structural Ramsey theory is a field on the boundary of combinatorics and model theory with deep connections to topological dynamics. Most of the known Ramsey classes in finite binary symmetric relational language can be shown to be Ramsey by utilizing a variant of the shortest path completion (e.g. Sauer's S-metric spaces, Conant's generalised metric spaces, Braunfeld's Λ-ultrametric spaces or Cherlin's metrically homogeneous graphs). In this thesis we explore the limits of the shortest path completion. We offer a unifying framework - semigroup-valued metric spaces - for all the aforementioned Ramsey classes and study their Ramsey expansions and EPPA (the extension property for partial automorphisms). Our results can be seen as evidence for the importance of studying the completion problem for amalgamation classes and have some further applications (such as the stationary independence relation). As a corollary of our general theorems, we reprove results of Hubička and Nešetřil on Sauer's S-metric spaces, results of Hubička, Nešetřil and the author on Conant's generalised metric spaces, Braunfeld's results on Λ-ultrametric spaces and the results of Aranda et al. on Cherlin's primitive 3-constrained metrically homogeneous graphs. We also solve several open problems such as EPPA for Λ-ultrametric...

For a positive integer $r$ and graphs $F$, $G$, and $H$, the graph Ramsey arrow notation $F \longrightarrow (G)^H_r$ means that for every $r$-colouring of the subgraphs of $F$ isomorphic to $H$, there exists a subgraph $G'$ of $F$ isomorphic to $G$ such that all the subgraphs of $G'$ isomorphic to $H$ are coloured the same. Graph Ramsey theory is the study of the graph Ramsey arrow and related arrow notations for other kinds of ``graphs" (\emph{e.g.}, ordered graphs, or hypergraphs). This thesis surveys finite graph Ramsey theory, that is, when all structures are finite. One aspect surveyed here is determining for which $G$, $H$, and $r$, there exists an $F$ such that $F \longrightarrow (G)^H_r$. The existence of such an $F$ is guaranteed when $H$ is complete, whether ``subgraph" means weak or induced, and existence results are also surveyed when $H$ is non-complete. When such an $F$ exists, other aspects are surveyed, such as determining the order of the smallest such $F$, finding such an $F$ in some restricted family of graphs, and describing the set of minimal such $F$'s. / February 2008

For a positive integer $r$ and graphs $F$, $G$, and $H$, the graph Ramsey arrow notation $F \longrightarrow (G)^H_r$ means that for every $r$-colouring of the subgraphs of $F$ isomorphic to $H$, there exists a subgraph $G'$ of $F$ isomorphic to $G$ such that all the subgraphs of $G'$ isomorphic to $H$ are coloured the same. Graph Ramsey theory is the study of the graph Ramsey arrow and related arrow notations for other kinds of ``graphs" (\emph{e.g.}, ordered graphs, or hypergraphs). This thesis surveys finite graph Ramsey theory, that is, when all structures are finite. One aspect surveyed here is determining for which $G$, $H$, and $r$, there exists an $F$ such that $F \longrightarrow (G)^H_r$. The existence of such an $F$ is guaranteed when $H$ is complete, whether ``subgraph" means weak or induced, and existence results are also surveyed when $H$ is non-complete. When such an $F$ exists, other aspects are surveyed, such as determining the order of the smallest such $F$, finding such an $F$ in some restricted family of graphs, and describing the set of minimal such $F$'s.

For a positive integer $r$ and graphs $F$, $G$, and $H$, the graph Ramsey arrow notation $F \longrightarrow (G)^H_r$ means that for every $r$-colouring of the subgraphs of $F$ isomorphic to $H$, there exists a subgraph $G'$ of $F$ isomorphic to $G$ such that all the subgraphs of $G'$ isomorphic to $H$ are coloured the same. Graph Ramsey theory is the study of the graph Ramsey arrow and related arrow notations for other kinds of ``graphs" (\emph{e.g.}, ordered graphs, or hypergraphs). This thesis surveys finite graph Ramsey theory, that is, when all structures are finite. One aspect surveyed here is determining for which $G$, $H$, and $r$, there exists an $F$ such that $F \longrightarrow (G)^H_r$. The existence of such an $F$ is guaranteed when $H$ is complete, whether ``subgraph" means weak or induced, and existence results are also surveyed when $H$ is non-complete. When such an $F$ exists, other aspects are surveyed, such as determining the order of the smallest such $F$, finding such an $F$ in some restricted family of graphs, and describing the set of minimal such $F$'s.