| Texto completo | |
| Autor(es): |
Número total de Autores: 3
|
| Afiliação do(s) autor(es): | [1] Beijing Inst Technol, Sch Math & Stat, Beijing - Peoples R China
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
[3] Tech Univ Ilmenau, Inst Math, D-98684 Ilmenau - Germany
Número total de Afiliações: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | COMBINATORICS PROBABILITY & COMPUTING; v. 30, n. 4, p. 570-590, JUL 2021. |
| Citações Web of Science: | 0 |
| Resumo | |
We prove that, for any t >= 3, there exists a constant c = c(t)> 0 such that any d-regular n-vertex graph with the second largest eigenvalue in absolute value. satisfying lambda <= cd(t-1)/n(t-2) contains vertex-disjoint copies of K-t covering all but at most n(1-1/(8t4)) vertices. This provides further support for the conjecture of Krivelevich, Sudakov and Szabo (Combinatorica 24 (2004), pp. 403-426) that (n, d, lambda)-graphs with n. 3N and lambda <= cd(2)/n for a suitably small absolute constant c > 0 contain triangle-factors. Our arguments combine tools from linear programming with probabilistic techniques, and apply them in a certain weighted setting. We expect this method will be applicable to other problems in the field. (AU) | |
| Processo FAPESP: | 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática |
| Beneficiário: | Guilherme Oliveira Mota |
| Modalidade de apoio: | Auxílio à Pesquisa - Jovens Pesquisadores |
| Processo FAPESP: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação |
| Beneficiário: | Carlos Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 14/18641-5 - Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos |
| Beneficiário: | Jie Han |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |