Друзья!
В этот вторник (02.06.26) На семинаре в 16 20 выступит Борис Гавриш. Прилагаем анонс.

Графовые подходы для справедливых дележей

В докладе будет рассмотрена модификация задачи о справедливом дележе (EFX), в которой игроки представлены вершинами графа, предметы — ребрами, а ориентация задает, кому достается предмет. Оказывается, что в такой постановке существование справедливого дележа зависит от хроматического числа графа: при 2 он всегда существует, в то время как при 4 и более для любого графа существуют оценки предметов, приводящие к его отсутствию.