Аннотация
In this paper, we show that every $(2^n-1+1)$-vertex induced subgraph of
the $n$-dimensional cube graph has maximum degree at least $n$. This
result is best possible, and improves a logarithmic lower bound shown by Chung,
Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that
the sensitivity and degree of a boolean function are polynomially related,
solving an outstanding foundational problem in theoretical computer science,
the Sensitivity Conjecture of Nisan and Szegedy.
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)