Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every k-edge-coloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring of G, we say c is a bad coloring if G contains no red K3or blue K1,t under c. A graph G is (H1,...,Hk)-Ramsey-minimal if G arrows (H1,...,Hk) but no proper subgraph of G has this property. Given a family F of graphs, we say that a graph G is F-saturated if no member of F is a subgraph of G, but for any edge xy not in E(G), G + xy contains a member of F as a subgraph. Letting Rmin(K3, K1,t) be the family of (K3,K1,t)-Ramsey minimal graphs, we study the saturation number, denoted sat(n,Rmin(K3,K1,t)), which is the minimum number of edges among all Rmin(K3,K1,t)-saturated graphs on n vertices. We believe the methods and constructions developed in this thesis will be useful in studying the saturation numbers of (K4,K1,t)-saturated graphs.

We examine different methods of generalize Van der Waerden's Theorem, the Multidimensional Van der Waerden Theorem, the Canonical Van der Waerden Theorem, and other Variants. / Master of Science

This thesis will study a variety of problems in graph theory. Initially, the focus will be on finding minimal degree conditions which guarantee the existence of various subgraphs. These subgraphs will all be formed of cycles, and this area of work will fall broadly into two main categories. First to be considered are cycles in edge-coloured graphs and, in particular, two questions of Li, Nikiforov and Schelp. It will be shown that a 2-edge-coloured graph with minimal degree at least 3n/4 either is isomorphic to the complete 4-partite graph with classes of order n/4, or contains monochromatic cycles of all lengths between 4 and n/2 (rounded up). This answers a conjecture of Li, Nikiforov and Schelp. Attention will then turn to the length of the longest monochromatic cycle in a 2-edge-coloured graph with minimal degree at least cn. In particular, a lower bound for this quantity will be proved which is asymptotically best possible. The next chapter of the thesis then shows that a hamiltonian graph with minimal degree at least (5-sqrt7)n/6 contains a 2-factor with two components. The thesis then concludes with a chapter about X_H, which is the number of copies of a graph H in the random graph G(n,p). In particular, it will be shown that, for a connected graph H, the value of X_H modulo k is approximately uniformly distributed, provided that k is not too large a function of n.

An online Ramsey game is a game between Builder and Painter, alternating in turns. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some round there is a monochromatic copy of the fixed graph H, otherwise Painter is the winner. In this thesis we investigate the computational complexity of the related decision problem and we show that it is PSPACE-complete. Moreover, we study a version of the game when Builder can draw only planar graphs and a generalization of the game for hypergraphs. We found a new class of graphs unavoidable on planar graphs. We provide a result showing that Builder wins the online Ramsey game on 3-uniform hyperforests when the goal graph H is 1-degenerate. 1

No description available.

Notre travail ici concerne certaines pistes pour des constructions nouveaux groupes, et en particulier de contre-exemples à la conjecture de Cherlin-Zilber. On parvient à trouver une réponse pour la stabilité de groupes CSA existentiellement clos. On exhibe un mot de groupe en deux variables qui a la propriété d'indépendance par rapport à la classe de groupes hyperboliques sans torsion. On en déduit que l'équation correspondante donne la propriété d'indépendance des groupes CSA existentiellement clos, ce qui en particulier implique leur instabilité. En outre, on prouve que les équations, et en particulier les ensembles définissables sans quantificateurs, définissent des ensembles stables dans les boules bornées des produits libres de groupes, en utilisant la version finie du théorème de Ramsey. Enfin, on introduit certains groupes construits comme tours particulières de produits libres et d'extensions HNN.

Thesis (M.C.S.)--Regent College, Vancouver, BC, 1992. / Abstract and vita. Includes bibliographical references (leaves 256-294).

In this dissertation we treat three tiling problems and three problems in combinatorial geometry, extremal graph theory and sparse Ramsey theory. We first consider tilings of $\mathbb{Z}^n$. In this setting a tile $T$ is just a finite subset of $\mathbb{Z}^n$. We say that $T$ tiles $\mathbb{Z}^n$ if the latter set admits a partition into isometric copies of $T$. Chalcraft observed that there exist $T$ that do not tile $\mathbb{Z}^n$ but tile $\mathbb{Z}^{d}$ for some $d > n$. He conjectured that such $d$ exists for any given tile. We prove this conjecture in Chapter 2. In Chapter 3 we prove a conjecture of Lonc, stating that for any poset $P$ of size a power of $2$, if $P$ has a greatest and a least element, then there is a positive integer $k$ such that $[2]^k$ can be partitioned into copies of $P$. The third tiling problem is about vertex-partitions of the hypercube graph $Q_n$. Offner asked: if $G$ is a subgraph of $Q_n$ such $|G|$ is a power of $2$, must $V(Q_d)$, for some $d$, admit a partition into isomorphic copies of $G$? In Chapter 4 we answer this question in the affirmative. We follow up with a question in combinatorial geometry. A line in a planar set $P$ is a maximal collinear subset of $P$. P\'or and Wood considered colourings of finite $P$ without large lines with a bounded number of colours. In particular, they examined whether monochromatic lines always appear in such colourings provided that $|P|$ is large. They conjectured that for all $k,l \ge 2$ there exists an $n \ge 2$ such that if $|P| \ge n$ and $P$ does not contain a line of cardinality larger than $l$, then every colouring of $P$ with $k$ colours produces a monochromatic line. In Chapter 5 we construct arbitrarily large counterexamples for the case $k=l=3$. We follow up with a problem in extremal graph theory. For any graph, we say that a given edge is triangular if it forms a triangle with two other edges. How few triangular edges can there be in a graph with $n$ vertices and $m$ edges? For sufficiently large $n$ we prove a conjecture of F\"uredi and Maleki that gives an exact formula for this minimum. This proof is given in Chapter 6. Finally, Chapter 7 is concerned with degrees of vertices in directed hypergraphs. One way to prescribe an orientation to an $r$-uniform graph $H$ is to assign for each of its edges one of the $r!$ possible orderings of its elements. Then, for any $p$-set of vertices $A$ and any $p$-set of indices $I \subset [r]$, we define the $I$-degree of $A$ to be the number of edges containing vertices $A$ in precisely the positions labelled by $I$. Caro and Hansberg were interested in determining whether a given $r$-uniform hypergraph admits an orientation where every set of $p$ vertices has some $I$-degree equal to $0$. They conjectured that a certain Hall-type condition is sufficient. We show that this is true for $r$ large, but false in general.

67f. / Submitted by Suelen Reis (suziy.ellen@gmail.com) on 2013-03-13T14:31:53Z No. of bitstreams: 1 Vinicius%20Cerqueiraseg.pdf: 867943 bytes, checksum: 490a06741857c66394129f9291181b00 (MD5) / Approved for entry into archive by Vania Magalhaes(magal@ufba.br) on 2013-03-14T12:30:40Z (GMT) No. of bitstreams: 1 Vinicius%20Cerqueiraseg.pdf: 867943 bytes, checksum: 490a06741857c66394129f9291181b00 (MD5) / Made available in DSpace on 2013-03-14T12:30:40Z (GMT). No. of bitstreams: 1 Vinicius%20Cerqueiraseg.pdf: 867943 bytes, checksum: 490a06741857c66394129f9291181b00 (MD5) Previous issue date: 2008 / Esta dissertação investiga o impacto do controle de capitais sobre o crescimento e o bem-estar em uma pequena economia aberta de um setor, sujeita a choques tecnológicos e com acesso limitado ao mercado internacional de capitais. A oferta de capitais é imperfeita devido à aversão ao risco por parte dos investidores internacionais. Os resultados do modelo mostram que, no caso dos controles diretos (quarentena) ou indiretos (imposto com alíquota decrescente em função do tempo de permanência na economia e equivalentes à quarentena), o impacto do controle de capitais é nulo sobre o crescimento e o bem-estar, não provocando mudança no equilíbrio em estado estacionário. No caso de controles indiretos com alíquota mínima independente do tempo de permanência na economia, há uma redução do bem-estar devido à diminuição do consumo por trabalhador efetivo no estado estacionário. / Salvador

This dissertation analyzes the theology and politics of Michael Ramsey between his ordination in 1928 and his retirement in 1974. Ramsey entered the priesthood after a burgeoning career in law and Liberal politics. I argue that Ramsey's later political activism as Archbishop of Canterbury was a continuation of his early political engagement at Cambridge. However, the Anglican Incarnational theological tradition exemplified in the writings of F. D. Maurice, Charles Gore, and William Temple exerted a powerful influence on Ramsey's politics after he entered the priesthood. This dissertation locates Ramsey within that Incarnational tradition, and I argue that the Incarnation was the locus not only of his theological writings and his historical writings on Anglican theology, but also of his political activism in the 1960s and early 1970s. I draw heavily on unpublished letters and autobiographical essays from the Ramsey Papers at Lambeth Palace, as well as on his speeches to ordinands and in House of Lords. Two chapters contain analyses of nearly all of Ramsey's published corpus, with one devoted to his historical writings and the other to his social theological writings. A third chapter analyzes three examples of Ramsey's activism at Canterbury (on legal reform for homosexual acts, the Rhodesian crisis of 1965, and Commonwealth immigration) within the context of his Incarnational social theology. I argue that the primary issue for Ramsey in each example was the affirmation of human dignity and conscience, regardless of race, religion, or sexual orientation, and that his belief in the post-Incarnational sanctification of humankind led him to emphasize the social values that he did.