O DMat parabeniza o aluno Gabriel Dias do Couto pela defesa de tese de doutorado realizada no dia 10 de abril de 2026.

Title: Deviations, Thresholds and Pursuits in Random Graphs

Abstract: In this thesis we study three problems in random graphs. We investigate the lower tail behaviour of the triangle count for moderate deviations, the connectivity threshold for random Friends and Strangers graphs, and the cop number of random hypergraphs.

In relation to the first problem, Neeman, Radin and Sadun discovered the rate associated with certain deviations in the number of triangles in random graphs. However, for a certain interval of deviations, in the lower tail, their bounds did not coincide. Answering a conjecture of theirs, we find the correct rate in this interval, up to a multiplicative constant.

For the second problem, we determine, up to a multiplicative constant, the threshold of connectivity of the Friends and Strangers graph $FS(G,H)$ with $G,H\sim G(n,p)$. Furthermore, our approach generalizes to the asymmetric case.

Finally, in the third, we study a problem of Cops and Robbers. The Conjecture of Meyniel, which asserts that $O(\sqrt{n})$ cops are sufficient for all connected graphs on $n$ vertices, is the central problem in this area of research. Pra\l at and Wormald showed that the conjecture is true ``typically" in the sense that it holds in graphs $G\sim G(n,p)$ with high probability. We prove a similar result in the context of random hypergraphs.

Banca Examinadora: 
Orientador: Simon Griffiths - PUC-Rio
Robert David Morris - IMPA
Maurício de Lemos Rodrigues Collares Neto - USP
Taísa Lopes Martins - UFF
Rangel Baldasso - PUC-Rio

Desejamos muito sucesso na sua caminhada!!