Thesis (MSc.)--University of Stellenbosch, 2000. / ENGLISH ABSTRACT: The notion of a classical graph theoretic Ramsey number is generalized by assuming that both the original graph whose edges are arbitrarily bicoloured and the monochromatic subgraphs to be forced are complete, balanced, multipartite graphs, instead of complete graphs as in the standard definition. Some small multipartite Ramsey numbers are found, while upper- and lower bounds are established for others. Analytic arguments as well as computer searches are used. / AFRIKAANSE OPSOMMING: Die klassieke grafiek-teoretiese definisie van ’n Ramsey getal word veralgemeen deur te aanvaar dat beide die oorspronklike grafiek, waarvan die lyne willekeurig met twee kleure gekleur word en die gesogte subgrafieke almal volledige, gebalanseerde, veelledige grafieke is, anders as in die standaard definisie. Klein veelledige Ramsey getalle word gevind, terwyl bo- en ondergrense vir ander daargestel word. Analitiese argumente en rekenaarsoektogte word gebruik.

In this dissertation, we are interested in studying several parameters of graphs and understanding their extreme values. We begin in Chapter~$2$ with a question on edge colouring. When can a partial proper edge colouring of a graph of maximum degree $\Delta$ be extended to a proper colouring of the entire graph using an `optimal' set of colours? Albertson and Moore conjectured this is always possible provided no two precoloured edges are within distance $2$. The main result of Chapter~$2$ comes close to proving this conjecture. Moreover, in Chapter~$3$, we completely answer the previous question for the class of planar graphs. Next, in Chapter~$4$, we investigate some Ramsey theoretical problems. We determine exactly what minimum degree a graph $G$ must have to guarantee that, for any two-colouring of $E(G)$, we can partition $V(G)$ into two parts where each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct colours. The following saturation problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger is considered in Chapter~$5$. Given a graph $H$ and a set of colours $\{1,2,\ldots,t\}$ (for some integer $t\geq |E(H)|$), we define $sat_{t}(n, R(H))$ to be the minimum number of $t$-coloured edges in a graph on $n$ vertices which does not contain a rainbow copy of $H$ but the addition of any non-edge in any colour from $\{1,2,\ldots,t\}$ creates such a copy. We prove several results concerning these extremal numbers. In particular, we determine the correct order of $sat_{t}(n, R(H))$, as a function of $n$, for every connected graph $H$ of minimum degree greater than $1$ and for every integer $t\geq e(H)$. In Chapter~$6$, we consider the following question: under what conditions does a Hamiltonian graph on $n$ vertices possess a second cycle of length at least $n-o(n)$? We prove that the `weak' assumption of a minimum degree greater or equal to $3$ guarantees the existence of such a long cycle. We solve two problems related to majority colouring in Chapter~$7$. This topic was recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number $k$, the smallest positive integer $m = m(k)$ such that every digraph can be coloured with $m$ colours, where each vertex has the same colour as at most a proportion of $\frac{1}{k}$ of its out-neighbours. Our main theorem states that $m(k) \in \{2k-1, 2k\}$. We study the following problem, raised by Caro and Yuster, in Chapter~$8$. Does every graph $G$ contain a `large' induced subgraph $H$ which has $k$ vertices of degree exactly $\Delta(H)$? We answer in the affirmative an approximate version of this question. Indeed, we prove that, for every $k$, there exists $g(k)$ such that any $n$ vertex graph $G$ with maximum degree $\Delta$ contains an induced subgraph $H$ with at least $n-g(k)\sqrt{\Delta}$ vertices such that $V(H)$ contains at least $k$ vertices of the same degree $d \ge \Delta(H)-g(k)$. This result is sharp up to the order of $g(k)$. %Subsequently, we investigate a concept called $\textit{path-pairability}$. A graph is said to be path-pairable if for any pairing of its vertices there exist a collection of edge-disjoint paths routing the the vertices of each pair. A question we are concerned here asks whether every planar path pairable graph on $n$ vertices must possess a vertex of degree linear in $n$. Indeed, we answer this question in the affirmative. We also sketch a proof resolving an analogous question for graphs embeddable on surfaces of bounded genus. Finally, in Chapter~$9$, we move on to examine $k$-linked tournaments. A tournament $T$ is said to be $k$-linked if for any two disjoint sets of vertices $\{x_1,\ldots ,x_k\}$ and $\{y_1,\dots,y_k\}$ there are directed vertex disjoint paths $P_1,\dots, P_k$ such that $P_i$ joins $x_i$ to $y_i$ for $i = 1,\ldots, k$. We prove that any $4k$ strongly-connected tournament with sufficiently large minimum out-degree is $k$-linked. This result comes close to proving a conjecture of Pokrovskiy.

Li, Nan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 88-90). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Literature on Illegal Immigration --- p.2 / Chapter 1.3 --- Literature on Income Distribution --- p.4 / Chapter 1.4 --- Outline and Contribution --- p.5 / Chapter 2 --- The Solow Model of Illegal Immigration --- p.7 / Chapter 2.1 --- The Basic Model --- p.7 / Chapter 2.2 --- Equilibrium and Transitional Dynamics --- p.10 / Chapter 2.2.1 --- Aggregate level --- p.10 / Chapter 2.2.2 --- Individual level --- p.12 / Chapter 3 --- Sensitivity Analysis in the Solow Model --- p.16 / Chapter 3.1 --- Benchmark Example --- p.16 / Chapter 3.2 --- Input Shares --- p.18 / Chapter 3.3 --- Share of Unskilled Labor 0 --- p.20 / Chapter 3.4 --- Different Initial Value of Capital --- p.21 / Chapter 4 --- The Ramsey Model of Illegal Immigration --- p.23 / Chapter 4.1 --- The Basic Model --- p.24 / Chapter 4.2 --- Transitional Dynamics and Equilibrium --- p.26 / Chapter 4.2.1 --- Transitional Dynamics --- p.26 / Chapter 4.2.2 --- Steady State --- p.27 / Chapter 5 --- Sensitivity Analysis in the Ramsey Model --- p.28 / Chapter 5.1 --- Benchmark Example --- p.29 / Chapter 5.2 --- Input Share --- p.30 / Chapter 5.3 --- Elasticity of Substitution 0 --- p.31 / Chapter 5.4 --- Penalty Ratio r --- p.32 / Chapter 5.5 --- Different Initial Value of Capital --- p.33 / Chapter 5.5.1 --- Case 1 k10 < k20 --- p.34 / Chapter 5.5.2 --- Case 2 k10 > k20 --- p.35 / Chapter 6 --- Comparison and Conclusion --- p.36

Dans ce document, nous étudions l’évitabilité de différentes formes de répétitions dans les mots. En particulier 3 des 6 chapitres sont dédiés aux répétitions abéliennes en lien notamment avec deux questions d’Erdős de 1957 et 1961. Nous commençons par montrer qu’il existe un algorithme décidant, sous certaines conditions, si un mot morphique évite des puissances abéliennes. Cet algorithme élargit la classe sur laquelle les précédents algorithmes pouvaient décider. Une généralisation de cet algorithme nous permet de montrer que les longs carrés abéliens sont évitables sur l’alphabet ternaire et que les carrés additifs sont évitables sur Z2 . Le premier résultat répond à une question ouverte de Mäkelä datant de 2003 alors que le deuxième rappelle la question ouverte de 1994 concernant l’évitabilité des carrés additifs sur Z.Une autre généralisation de notre algorithme permet d’étudier l’évitabilité des motifs au sens abélien. Nous montrons que les motifs binaires de longueur supérieure à 14 sont évitables sur l’alphabet binaire, améliorant la précédente borne de 118.Nous donnons des conditions suffisantes pour qu’un morphisme soit sans longues puissances nème k-abéliennes. Ce résultat nous permet de calculer, pour tout k ≥ 3, le nombre minimum de carrés k-abéliens qu’un mot binaire infini doit contenir en facteur. Il permet aussi de montrer que les longs carrés 2-abéliens sont évitables sur l’alphabet binaire et qu’il existe un mot ternaire qui ne contient qu’un seul carré 2-abélien en tant que facteur.Enfin, nous proposons une classification complète des formules binaires en fonction de la taille d’alphabet qu’il faut pour les éviter et du taux de croissance (exponentiel ou polynomial) du langage les évitant. / In this document, we study the avoidability of different kind of repetitions in words. We firstshow that under some conditions one can decide whether a morphic word avoids abelian n-thpowers. This algorithm can decide over a wider class of morphism than the previousalgorithms. We generalize this algorithm and use it to show that long abelian squares areavoidable over the ternary alphabet and that additive squares are avoidable over Z2 . The firstresult answers a weak version of a question formulated by Mäkelä in 2003 and the second oneis related to an open question from 1994 about the avoidability of additive squares over Z.Another generalization of this algorithm can be used to study avoidability of patterns in theabelian sense. In particular, we show that binary patterns of length more than 14 areavoidable over the binary alphabet in the abelian sense. This improves considerably theprevious bound of 118.We give sufficient conditions for a morphism to be long k-abelian n-th power-free. This resultallows us to compute for every k ≥ 3 the number of different k-abelian squares that a binaryword must contain. We prove that long 2-abelian squares are avoidable over the binaryalphabet and that over the ternary alphabet there exists a word that contains only one 2-abelian square.We also give a complete classification of binary formulas based on the size of the smallestalphabet over which they are avoidable and on the growth (exponential or polynomial) of theassociated language.

A bounded and linear operator is said to be hypercyclic if there exists a vector such that its orbit under the action of the operator is dense. The first example of a hypercyclic operator on a Banach space was given in 1969 by Rolewicz who showed that if B is the unweighted unilateral backward shift on l 2 , then λB is hypercyclic if and only if |λ| > 1. Among its features, we can mention for example that finite-dimensional spaces cannot support hypercyclic operators, proved by Kitai. On the other hand, several people have shown in different contexts, in the Hilbert space frame, that the set of hypercyclic vectors for a hypercyclic operator is a Gδ dense set. This thesis is divided into four chapters. In the first one, we give some preliminaries by mentioning some definitions and known results that will be of great help later. In chapter 2, we introduce a refinement of the notion of hypercyclicity, relative to the set N(U, V ) = {n ∈ N : T −nU ∩ V 6= ∅} when belonging to a certain collection F of subsets of N, namely a bounded and linear operator T is called F-operator if N(U, V ) ∈ F, for any pair of non-empty open sets U, V in X. First, we do an analysis of the hierarchy established between F-operators, whenever F covers those families mostly studied in Ramsey theory. Second, we investigate which kind of properties of density can have the sets N(x, U) = {n ∈ N : T nx ∈ U} and N(U, V ) for a given hypercyclic operator, and classify the hypercyclic operators accordingly to these properties. In chapter three, we introduce the following notion: an operator T on X satisfies property PF if for any U non-empty open set in X, there exists x ∈ X such that N(x, U) ∈ F. Let BD the collection of sets in N with positive upper Banach density. We generalize the main result of a paper due to Costakis and Parissis using a strong result of Bergelson and Mccutcheon in the vein of Szemerédi’s theorem, leading us to a characterization of those operators satisfying property PBD. It turns out that operators having property PBD satisfy a kind of recurrence described in terms of essential idempotents of βN (the Stone-Čech compactification of N). We will discuss the case of weighted backward shifts satisfying property PBD. On the other hand, as a consequence we obtain a characterization of reiteratively hypercyclic operators, i.e. operators for which there exists x ∈ X such that for any U non-empty open set in X, the set N(x, U) ∈ BD. The fourth chapter focuses on a refinement of the notion of disjoint hypercyclicity. We extend a result of Bès, Martin, Peris and Shkarin by stating: Bw is F-weighted backward shift if and only if (Bw, . . . , Br w) is d-F, for any r ∈ N, where F runs along some filters containing strictly the family of cofi- nite sets, which are frequently used in Ramsey theory. On the other hand, we point out that this phenomenon does not occur beyond the weighted shift frame by showing a mixing linear operator T on a Hilbert space such that the tuple (T, T2 ) is not d-syndetic. We also, investigate the relationship between reiteratively hypercyclic operators and d-F tuples, for filters F contained in the family of syndetic sets. Finally, we examine conditions to impose in order to get reiterative hypercyclicity from syndeticity in the weighted shift frame. / Puig De Dios, Y. (2014). Recurrence in Linear Dynamics [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/48473 / TESIS

No description available.

No description available.

No description available.

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.

No description available.