Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/50244
Title in Portuguese: On Ramsey property for random graphs.
Title: On Ramsey property for random graphs.
Author: Santos, Walner Mendonça dos
Advisor(s): Benevides, Fabrício Siqueira
Keywords: Ramsey property
Binomial random graph
Threshold function
Propriedade de Ramsey
Grafo aleatório binomial
Função limiar
Issue Date: 16-Aug-2016
Citation: SANTOS, Walner Mendonça dos. On Ramsey property for random graphs. 2016. 67 f. Dissertação (Mestrado Acadêmico em Matemática) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2016.
Abstract in Portuguese: Um grafo G é Ramsey para um par de grafos (F1, F2) se em toda 2-aresta-coloração de G for possível encontrar cópias monocromáticas de F1 com a primeira cor ou cópias monocromáticas de F2 com a segunda cor. O grafo aleatório binomial Gn,p é um subgrafo de Kn, o grafo completo com n vértices, obtido escolhendo cada aresta de Kn independentemente e aleatoriamente com probabilidade p para pertencer à Gn,p. Para um grafo F, seja m2(F) o valor máximo de d(F0) = (e(F0) − 1)/(v(F0) − 2) dentre todos os subgrafos F0 ⊆ F com v(F0) ≥ 3. Se tal máximo é atingido por F0 = F, então dizemos que F é 2-balanceado. Ademais, dizemos que F é estritamente 2-balanceado se d2(F) > d2(F0) para todo subgrafo próprio F0 de F com v(F0) ≥ 3. Para um par de grafos (F1, F2), seja m2(F1, F2) o valor máximo de e(F01)/(v(F01) − 2 + 1/m2(F2)) dentre todos os subgrafos F01⊆ F 1 com v(F01) ≥ 3. Esta dissertação objetiva-se em apresentar uma prova de que para todo par de grafos (F1, F2) tais que F1 é 2-balanceado e m2(F1) > m2(F2) > 1 ou F1 é estritamente 2-balanceado e m2(F1) ≥ m2(F2) > 1, existe uma constante positiva C para o qual assimptoticamente quase certamente, Gn,p é Ramsey para o par (F1, F2), sempre que p ≥ Cn−1/m2(F1,F2) . Este resultado foi conjeturado por Kohayakawa and Kreuter em 1997 sem a condição de balanceamento sobre F1. A prova do principal teorema nesta dissertação deverá usar técnicas desenvolvidas recentemente e conhecidas como hypergraph containers.
Abstract: A graph G is Ramsey for a pair of graphs (F 1 , F 2 ) if in every 2-edge-colouring of G, one can find a monochromatic copy of F 1 with the first colour or a monochromatic copy of F 2 with the second colour. The binomial random graph G n,p is a subgraph of K n , the complete graph on n vertices, obtained by choosing each edge of K n independently at random with probability p to belong to G n,p . For a graph F, let m 2 (F) be the maximum of d 2 (F0) = (e(F0) − 1)/(v(F0) − 2) over all the subgraphs F0 ⊆ F with v(F0) ≥ 3. If this maximum is reached for F0 = F, then we say that F is 2-balanced. Furthermore, we say that F is strictly 2-balanced if d 2 (F) > d 2 (F0), for all proper subgraph F0 of F with v(F0) ≥ 3. For a pair of graphs (F 1 , F 2 ), let m 2 (F 1 , F 2 ) be the maximum of e(F01)/(v(F01) − 2 + 1/m 2 (F 2 )) over all the subgraphs F01⊆ F 1 with v(F01) ≥ 3. This dissertation aims to present a proof that for every pair of graphs (F 1 , F 2 ) such that F 1 is 2-balanced and m 2 (F 1 ) > m 2 (F 2 ) > 1 or F 1 is strictly 2-balanced and m 2 (F 1 ) ≥ m 2 (F 2 ) > 1, there exists a positive constant C for which asymptotically almost surely G n,p is Ramsey for the pair (F 1 , F 2 ), whenever that p ≥ Cn−1/m2(F1,F2). This result was conjectured by Kohayakawa and Kreuter in 1997 without the balancing condition over F1. The proof of the main theorem uses a recently developed technique known as hypergraph containers.
URI: http://www.repositorio.ufc.br/handle/riufc/50244
metadata.dc.type: Dissertação
Appears in Collections:DMAT - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2016_dis_wmsantos.pdfdissertaçao walner mendonça468,59 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.