| Texto completo | |
| Autor(es): |
Alvarado, Jose D.
;
do Couto, Gabriel Dias
;
Griffiths, Simon
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | EUROPEAN JOURNAL OF COMBINATORICS; v. 129, p. 29-pg., 2025-10-01. |
| Resumo | |
Let N triangle(G)be the number of triangles in a graph G. In Gold-schmidt et al.(2020) and Neeman et al.(2023)(respectively) the following bounds were proved on the lower tail behaviour of triangle counts in the dense Erdos-Renyi random graphs G(m)similar to G (n, m): P(N-triangle(G((m)))<(1-delta)E[N-triangle(G((m)))]) ={exp(-Theta(delta(2)n(3)))ifn-3/2 <<delta << n(-1) exp(-Theta(delta(2)/(3)n(2)))ifn-3/4 <<delta << 1. Neeman et al.(2023)also conjectured that the probability should be of the form exp(-Theta(delta(2)n(3)))inthe''missinginterval''n(-1)<<delta << n(-3/4).We prove this conjecture. As part of our proof we also prove that some random graph statistics, related to degrees and codegrees, are normally dis-tributed with high probability. (c) 2025 Elsevier Ltd. All rights are reserved ,including those for text and datamining ,AI training, and similar technologies. (AU) | |
| Processo FAPESP: | 20/10796-0 - Problemas estruturais em grafos aleatórios |
| Beneficiário: | José Diego Alvarado Morales |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |