Laboratory of Mathematical Logic at PDMI

Вторник, 23 ноября, комната 106. Начало в 18:00.

23 ноября.
Д.В.Карпов, доклад по статье
D.Achlioptas, M.Molloy "Almost all graphs with 2.522N edges are not 3-colorable". (The Electronic Journal of Combinatorics, 6(1999), #R29)
Abstract. B этой работе доказывается, что для любого с>=2.522, вершины случайного графа с N вершинами и 2.522N ребрами нельзя правильным образом раскрасить в три цвета с вероятностью 1-o(1). Также в этой работе рассматтривается рассматривается аналогичный вопрос для k-раскрашиваемости при k>3, приводятся соответствующие оценки.