Laboratory of Mathematical Logic at PDMI

Пятница, 7 декабря, комната 106. Начало в 17:45.

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

Тема: О покрытии графа двудольными кликами.

Abstract

В докладе будет рассказано несколько новых (полученных автором совместно со Стасисом Йукной) оценок на количество двудольных клик, необходимых для покрытия всех ребер графа. Эта сама по себе интересная задача имеет применения в таких областях, как коммуникационная сложность и сложность схем. В конце доклада будут таже представлены несколько открытых вопросов.