Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Triangle-Free Subgraphs of Random Graphs

Texto completo
Autor(es):
Allen, Peter [1] ; Bottcher, Julia [1] ; Kohayakawa, Yoshiharu [2] ; Roberts, Barnaby [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] London Sch Econ & Polit Sci, Dept Math, Houghton St, London WC2A 2AE - England
[2] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: COMBINATORICS PROBABILITY & COMPUTING; v. 27, n. 2, p. 141-161, MAR 2018.
Citações Web of Science: 0
Resumo

Recently there has been much interest in studying random graph analogues of well-known classical results in extremal graph theory. Here we follow this trend and investigate the structure of triangle-free subgraphs of G(n, p) with high minimum degree. We prove that asymptotically almost surely each triangle-free spanning subgraph of G(n, p) with minimum degree at least (2/5 + o(1)) pn is O(p(-1)n)-close to bipartite, and each spanning triangle-free subgraph of G(n, p) with minimum degree at least (1/3 + epsilon) pn is O(p(-1)n)-close to r-partite for some r = r(e). These are random graph analogues of a result by Andrasfai, Erdos and Sos (Discrete Math. 8 (1974), 205-218), and a result by Thomassen (Combinatorica 22 (2002), 591-596). We also show that our results are best possible up to a constant factor. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
Beneficiário:Jefferson Antonio Galves
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs