Leírás
Előadók: Csóka Endre & Harangi Viktor
Cím: Independent sets on random regular graphs
Absztrakt: The talk is about the independence ratio of large random d-regular graphs with a constant degree d. There is a conjectured formula about the independence ratio for d ≥ 20, based on statistical physics methods. The breakthrough paper of Ding, Sly, and Sun rigorously proved it for (very) large d. The fact that the Ding-Sly-Sun proof works only for large d is not simply due to technical issues: there is a surprising phase transition at d ≈ 19.14, and their proof idea can work only if we are well above this threshold. Even more intriguing is the regime below the threshold where we did not even have a conjecture for the formula. We will briefly present the Ding-Sly-Sun approach and sketch our progress and new ideas, both above and below the threshold.