Thesis (Ph. D.)--University of Chicago, Divinity School, December 2000. / Includes bibliographical references. Also available on the Internet.

No description available.

No description available.

Ingeniero Civil Matemático / La presente memoria tiene como objetivo un estudio general sobre componentes monocromáticas en multicoloreos de aristas de grafos completos, o dicho de otro modo, un coloreo de aristas de multigrafos completos. En particular, el tema de mayor importancia consiste en una generalización de una importante clase de problemas relacionados con la Conjetura de Ryser, la cual habla de una cota universal para el número de componentes conexas monocromáticas necesarias para cubrir todos los vértices de un grafo con sus aristas coloreadas, y donde tal cota solo depende del número de colores utilizados. Los resultados presentes en la memoria son fruto de distintas formas de abordar determinados problemas relacionados con la generalización mencionada y que, por fortuna, resultaron no solo ser útiles para los propósitos para los que fueron ideados, sino que algunos de ellos poseen interés por sí mismos. En primer lugar el motivo de estudio se centra en la cantidad de vértices que podemos asegurar para alguna de las componentes monocromáticas inducidas en un multicoloreo de aristas arbitrario en grafos bipartitos, para luego extender el resultado a grafos completos. Posteriormente se estudia una cota de vértices para multicoloreos de grafos tales que pueden ser cubiertos con tres componentes conexas monocromáticas y no pueden ser cubiertos con dos componentes conexas monocromáticas, pero si aislamos cualquiera de sus vértices entonces el resto de ellos pueden ser cubiertos por dos componentes monocromáticas. Este tipo de multicoloreos será llamado 3-crítico. Finalmente se introduce la generalización de un caso particular de la Conjetura de Ryser, que consiste en encontrar cotas, dependientes del número de colores utilizados, para multicoloreos de aristas de grafos completos. En particular, se restringe el estudio para multicoloreos de aristas uniformes, los cuales se definen como multicoloreos donde todas las aristas tienen el mismo número de colores. Primero se muestran cotas superiores generales, luego cotas inferiores, para finalmente estudiar determinados casos de manera particular y concluir cotas de manera estricta.

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.

Serviços de telecomunicações são importantes não apenas pela sua característica de setor de infra-estrutura mas também pelo seus potenciais efeitos de spill over. A universalização dos serviços de telecomunicações tem sido uma parte importante da intervenção regulatória. As justificativas podem ser econômicas: externalidades de rede, ou não econômicas: cidadania e coesão social. Das várias possibilidades alternativas de políticas, apresenta-se a implementação dos preços de Ramsey, através de markup, como um meio de minimizar as perdas de eficiência econômica na consecução ao deste objetivo, a partir de diferentes cenários de estruturas de mercado e valores de parâmetros. / Telecommunications services are relevant, not only due to its infra-structure service characteristic, but also for their spill over potential effects. Telecommunication suniversal service has been a relevant piece of the regulatory process. Economic reasons might be network externalities; whilst non-economic, citizenship and social cohesion. Among the alternative policy possibilities, it is suggested the implementa-tion of Ramsey pricing, through markup, as a mean to minimize the loss of economic efficiency in reaching this purpose, from different market structures scenarios and parameters values.

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.

Serviços de telecomunicações são importantes não apenas pela sua característica de setor de infra-estrutura mas também pelo seus potenciais efeitos de spill over. A universalização dos serviços de telecomunicações tem sido uma parte importante da intervenção regulatória. As justificativas podem ser econômicas: externalidades de rede, ou não econômicas: cidadania e coesão social. Das várias possibilidades alternativas de políticas, apresenta-se a implementação dos preços de Ramsey, através de markup, como um meio de minimizar as perdas de eficiência econômica na consecução ao deste objetivo, a partir de diferentes cenários de estruturas de mercado e valores de parâmetros. / Telecommunications services are relevant, not only due to its infra-structure service characteristic, but also for their spill over potential effects. Telecommunication suniversal service has been a relevant piece of the regulatory process. Economic reasons might be network externalities; whilst non-economic, citizenship and social cohesion. Among the alternative policy possibilities, it is suggested the implementa-tion of Ramsey pricing, through markup, as a mean to minimize the loss of economic efficiency in reaching this purpose, from different market structures scenarios and parameters values.

Thesis (M.S.)--Rochester Institute of Technology, 2004. / Typescript. Includes bibliographical references (leaves 71-75).

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / 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. / 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.