Laboratory of Mathematical Logic at PDMI

Вторник, 4 апреля, комната 412. Начало в 15:00.

Докладчик: А. Косовская.

ОПИСАНИЕ ХРОМАТИЧЕСКОГО ЧИСЛА ГРАФА И ЧИСЛА НЕЗАВИСИМОСТИ С ПОМОЩЬЮ ПОЛИНОМА, ОПРЕДЕЛЯЕМОГО ГРАФОМ
Будут рассказаны связи между некоторым полиномом, задаваемым графом и числовыми характеристиками этого графа. отсюда выводятся некоторые оценки на число независимости графа. В частности, будут рассказаны результаты статьи L.Lovasz "Stable set and polynomials". Доклад тематически связан с докладом Д.Карпова и Ю.В.матиясевича 21 декабря 1999 года.