Семинар Международной лаборатории теоретической информатики: Perfect matchings in cubic bridgeless graphs
В четверг, 27 июня, приглашаем вас с 18:10 до 19:30 на семинар лаборатории ТИ в аудитории R407, Покровский бульвар, 11.
Название доклада: Perfect matchings in cubic bridgeless graphs
Докладчик: Никита Мануйленко
Аннотация:
Cubic bridgeless graphs admit a perfect matching. This fact was first proven by Petersen by the late nineteenth century. A few years later, in 2011, Esperet, Kard\v{o}s, King, Kr\'{a}l and Norine provided the first exponential lower bound $2^{|V|/3656}$ on the number of perfect matchings in cubic bridgeless graphs (a result conjectured in the seventies by Lov\'asz and Plummer). After studying their research, we found out that part of the proof can be improved to achieve a better bound of $2^{|V|/1920}$.