Os principais objetos de estudo neste trabalho são os números de Ramsey para circuitos e o lema da regularidade de Szemerédi. Dados grafos $L_1, \\ldots, L_k$, o número de Ramsey $R(L_1,\\ldots,L_k)$ é o menor inteiro $N$ tal que, para qualquer coloração com $k$ cores das arestas do grafo completo com $N$ vértices, existe uma cor $i$ para a qual a classe de cor correspondente contém $L_i$ como um subgrafo. Estaremos especialmente interessados no caso em que os grafos $L_i$ são circuitos. Obtemos um resultado original solucionando o caso em que $k=3$ e $L_i$ são circuitos pares de mesmo tamanho. / The main objects of interest in this work are the Ramsey numbers for cycles and the Szemerédi regularity lemma. For graphs $L_1, \\ldots, L_k$, the Ramsey number $R(L_1, \\ldots,L_k)$ is the minimum integer $N$ such that for any edge-coloring of the complete graph with~$N$ vertices by $k$ colors there exists a color $i$ for which the corresponding color class contains~$L_i$ as a subgraph. We are specially interested in the case where the graphs $L_i$ are cycles. We obtained an original result solving the case where $k=3$ and $L_i$ are even cycles of the same length.

Dois problemas combinatórios são estudados: (i) determinar a quantidade de cópias de um hipergrafo fixo em um hipergrafo uniforme pseudoaleatório, e (ii) estimar números de Ramsey de ordem dois e três para grafos com largura de banda pequena e grau máximo limitado. Apresentamos um lema de contagem para estimar a quantidade de cópias de um hipergrafo k-uniforme linear livre de conectores (conector é uma generalização de triângulo, para hipergrafos) que estão presentes em um hipergrafo esparso pseudoaleatório G. Considere um hipergrafo k-uniforme linear H que é livre de conectores e um hipergrafo k-uniforme G com n vértices. Seja d_H=\\max\\{\\delta(J): J\\subset H\\} e D_H=\\min\\{k d_H,\\Delta(H)\\}. Estabelecemos que, se os vértices de G não possuem grau grande, famílias pequenas de conjuntos de k-1 elementos de V(G) não possuem vizinhança comum grande, e a maioria dos pares de conjuntos em {V(G)\\choose k-1} possuem a quantidade ``correta\'\' de vizinhos, então a quantidade de imersões de H em G é (1+o(1))n^{|V(H)|}p^{|E(H)|}, desde que p\\gg n^{1/D_H} e |E(G)|={n\\choose k}p. Isso generaliza um resultado de Kohayakawa, Rödl e Sissokho [Embedding graphs with bounded degree in sparse pseudo\\-random graphs, Israel J. Math. 139 (2004), 93--137], que provaram que, para p dado como acima, esse lema de imersão vale para grafos, onde H é um grafo livre de triângulos. Determinamos assintoticamente os números de Ramsey de ordem dois e três para grafos bipartidos com largura de banda pequena e grau máximo limitado. Mais especificamente, determinamos assintoticamente o número de Ramsey de ordem dois para grafos bipartidos com largura de banda pequena e grau máximo limitado, e o número de Ramsey de ordem três para tais grafos, com a suposição adicional de que ambas as classes do grafo bipartido têm aproximadamente o mesmo tamanho. / Two combinatorial problems are studied: (i) determining the number of copies of a fixed hipergraph in uniform pseudorandom hypergraphs, and (ii) estimating the two and three color Ramsey numbers for graphs with small bandwidth and bounded maximum degree. We give a counting lemma for the number of copies of linear k-uniform \\emph hypergraphs (connector is a generalization of triangle for hypergraphs) that are contained in some sparse hypergraphs G. Let H be a linear k-uniform connector-free hypergraph and let G be a k-uniform hypergraph with n vertices. Set d_H=\\max\\{\\delta(J)\\colon J\\subset H\\} and D_H=\\min\\{kd_H,\\Delta(H)\\}. We proved that if the vertices of G do not have large degree, small families of (k-1)-element sets of V(G) do not have large common neighbourhood and most of the pairs of sets in {V(G)\\choose k-1} have the `right\' number of common neighbours, then the number of embeddings of H in G is (1+o(1))n^p^, given that p\\gg n^ and |E(G)|=p. This generalizes a result by Kohayakawa, R\\\"odl and Sissokho [Embedding graphs with bounded degree in sparse pseudo\\-random graphs, Israel J. Math. 139 (2004), 93--137], who proved that, for p as above, this result holds for graphs, where H is a triangle-free graph. We determine asymptotically the two and three Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that both classes of the bipartite graph have almost the same size.

Thesis--Lutheran University, Waterloo, Ont. / Includes bibliographical references.

OLIVEIRA, Marcelo Mendes de; ROGÉRIO, José Robério. Aplicações da teoria dos grafos à teoria dos grupos. 2008. 74 f. Dissertação (mestrado)- Universidade Federal do Ceará, Pós-Graduação em Matemática, Fortaleza-CE, 2008. / Submitted by Rocilda Sales (rocilda@ufc.br) on 2011-10-27T13:30:47Z No. of bitstreams: 1 2008_dis_mmoliveira.pdf: 349878 bytes, checksum: d6439d5ec62ea18056a42540326a4abe (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2011-10-27T13:33:08Z (GMT) No. of bitstreams: 1 2008_dis_mmoliveira.pdf: 349878 bytes, checksum: d6439d5ec62ea18056a42540326a4abe (MD5) / Made available in DSpace on 2011-10-27T13:33:08Z (GMT). No. of bitstreams: 1 2008_dis_mmoliveira.pdf: 349878 bytes, checksum: d6439d5ec62ea18056a42540326a4abe (MD5) Previous issue date: 2008 / This report deals with applications of Graph Theory to Group Theory. Once we construct the graph associated to a finite group, we get several interesting results on the group structure by analysing its associated graph with the help of various standard graph-theoretic tools. More precisely, the chromatic and independence numbers of the graph of a finite group allows us to estimate the maximal cardinality of an abelian subgroup of it, as well as the minimal size of a subset of the group, all of whose elements don’t commute in pairs; for finite abelian groups, we also study their free-sum subsets. / O propósito desta dissertação é apresentar aplicações da Teoria dos Grafos à Teoria dos Grupos. De posse do grafo associado a um grupo finito, nós obtemos vários resultados interessantes sobre a estrutura do grupo analisando tal grafo à luz de técnicas-padrão da Teoria dos Grafos. Mais precisamente, os números cromático e de independência do grafo de um grupo finito nos permitem estimar a cardinalidade máxima de um subgrupo abeliano do mesmo, bem como o tamanho mínimo possível de um subconjunto do grupo formado por elementos que não comutam dois a dois; no caso de grupos finitos abelianos, nós também estudamos seus subconjuntos livres de somas.

<p> This thesis gives new finite and asymptotic estimates of the Ramsey numbers using certain number-theoretical considerations; it also contains a brief historical survey on determination of Ramsey numbers and related number-theoretical problems.</p> / Thesis / Master of Science (MSc)

<p> This thesis studies a number of issues in optimal fiscal and monetary policy using the Ramsey framework. Specifically, it focuses on the effects of learning-by-doing and organizational capital on optimal policy responses. The first essay investigates the optimal capital income taxation in presence of learning-by-doing effects. The main result is that the optimal tax rate on capital income is significantly positive in the long run even though the product market is imperfectly competitive. This finding contrasts with results obtained in the literature that the capital income tax should be zero if the product market is perfectly competitive and negative if the product market is imperfectly competitive. The second essay studies the effects of learning-by-doing, and price rigidities on the dynamic properties of optimal fiscal and monetary policy variables. The m~in result is that, contrary to the findings of other papers in this literature, optimal Ramsey inflation is very stable and persistent over the business cycle. A second important result is that optimal tax policy is counter-cyclical - tax rates fall during recession and rise during boom. This finding contrasts with pro-cyclical tax results obtained in standard sticky price Ramsey models. Finally, the third essay studies welfare maximizing fiscal and monetary policy rules in a model with sticky prices, learning-by-doing in the technology, and distortionary taxation. Specifically, it considers monetary feedback rules whereby the nominal interest rate is set as a function of 'output and inflation. The main finding is that the optimal interest-rate rules call for a very strong response to inflation and a very weak response to output. Also, the optimal interest-rate rules are forward looking. This result contrasts with the backward looking optimal interest rate rules obtained in the existing optimal policy literature. The optimized fiscal rule is passive in the sense that tax revenues increase only mildly in response to increases in government liabilities. The optimized regime yields a level of welfare that is very close to that implied by the Ramsey optimal policy. </p> / Thesis / Doctor of Philosophy (PhD)

The Ramsey number $R(r, b)$ is the least positive integer such that every edge 2-coloring of the complete graph $K_{R(r, b)}$ with colors red and blue either embeds a red $K_r$ or a blue $K_b$. We explore various methods to find lower bounds on $R(r,b)$, finding new results on fibrations and semicirculant graphs. Then, generalizing the Ramsey number to graphs other than complete graphs, we flesh out the missing details in the literature on a theorem that completely determines the generalized Ramsey number for cycles.

This thesis is written as a single source introduction to Ramsey Theory for advanced undergraduates and graduate students. / Master of Science

No description available.

No description available.