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.)

Finding any given 2-factor in sparse pseudorandom graphs efficiently

Texto completo
Autor(es):
Han, Jie [1] ; Kohayakawa, Yoshiharu [2] ; Morris, Patrick [3, 4] ; Person, Yury [5]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Rhode Isl, Dept Math, 5 Lippitt Rd, Kingston, RI 02881 - USA
[2] Univ Sao Paulo, Inst Matemat Estat, Sao Paulo - Brazil
[3] Berlin Math Sch, Berlin - Germany
[4] Free Univ Berlin, Inst Math, Berlin - Germany
[5] Tech Univ, Inst Math, Ilmenau - Germany
Número total de Afiliações: 5
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF GRAPH THEORY; MAY 2020.
Citações Web of Science: 0
Resumo

Given an n-vertex pseudorandom graph G and an n-vertex graph H with maximum degree at most two, we wish to find a copy of H in G, that is, an embedding phi:V(H)-> V(G) so that phi(u)phi(v)is an element of E(G) for all uv is an element of E(H). Particular instances of this problem include finding a triangle-factor and finding a Hamilton cycle in G. Here, we provide a deterministic polynomial time algorithm that finds a given H in any suitably pseudorandom graph G. The pseudorandom graphs we consider are (p,lambda)-bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, omega(pn). A (p,lambda)-bijumbled graph is characterised through the discrepancy property: |e(A,B)-p|A||B||<lambda|A||B| for any two sets of vertices A and B. Our condition lambda=O(p2n/logn) on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption-reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications. (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: 14/18641-5 - Circuitos Hamiltonianos e problemas de ladrilhamento em hipergrafos
Beneficiário:Jie Han
Linha de fomento: Bolsas no Brasil - Pós-Doutorado