Endre Csóka: Random graphs and independent sets

Speaker: Endre Csóka

Title: Random graphs and independent sets 

Abstract: We want to understand large random bounded-degree graphs via their substructures, e.g. the maximum size of independent sets or cuts. We had many new results about it in the last few years, including local algorithms, entropy bounds and statistical physics methods including replica symmetry, cavity method, hard core model, spin glasses, free energy, etc. For example, the best bounds for the independence ratio on random 3-regular graphs improved from [0.4375, 0.4554] to [0.4453, 4509] by these new techniques in the last few years, with a suggestion that local algorithms can reach the optimal ratio.

This talk is also an initiative for deeply understanding the statistical physics approach in order to combine them with our pure mathematics approach. It seems that nobody really understands both topics - I only started to understand the statistical physics techniques - but I believe that it could be very fruitful to combine these two approaches.