Поредната сбирка на

Националния семинар по стохастика

ще се проведе на 8 ноември 2023 г. (сряда) от 14:00 часа в зала 503 на ИМИ – БАН.

Доклад на тема

Hamiltonicity of randomly perturbed graphs

ще изнесе

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

Абстракт: 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.