О нижней оценке порога 4-выполнимости

Пусть $F_k(n,m)$ – случайная $k$-конъюнктивная нормальная форма, полученная путем равновероятного и независимого выбора $m$ скобок из числа всех $k$-буквенных скобок над множеством из $n$ переменных. Доказывается, что если $F_4(n, rn)$ невыполнима с вероятностью, стремящейся к 1 при $n\to\infty$, то $r\ge8.09$. Тем самым улучшена известная нижняя оценка $r\ge7.91$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 04-01-00359.