The next meeting of the

National Seminar on Probability and Statistics

will be held on November 8, 2023, at 2:00 p.m. in Room 503 of the Institute of Mathematics and Informatics.

A talk on:

Hamiltonicity of randomly perturbed graphs

will be delivered by

Alberto Espuny Díaz (Postdoctoral researcher at Universität Heidelberg, Germany).

Abstract. In parallel to the development of smoothed analysis of algorithms, the study of randomly perturbed graphs has thrived in the combinatorics community. The setup is the following: one considers a dense graph $H$ which fails to satisfy some increasing property and then sprinkles edges randomly until the property appears. A main goal in the area is to understand how many random edges are needed, and which graphs $H$ are “worst” for this problem.

In this talk I will survey some results in the area and focus particularly on the Hamiltonicity problem, which has often been used as a test for many techniques in graph theory. I will present several variants of the problem, as well as some results for each of these variants. The talk is based on joint works with Alexander Allin, António Girão, and Joseph Hyde.