Geodesic
A lower bound for the 4-satisfiability threshold
Diskretnaya Matematika, Tome 19 (2007) no. 2, pp. 101-108

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $F_k(n,m)$ be a random $k$-conjunctive normal form obtained by selecting uniformly and independently $m$ out of all possible $k$-clauses on $n$ variables. We prove that if $F_4(n,rn)$ is unsatisfiable with probability tending to one as $n\to\infty$, then $r\ge8.09$. This sharpens the known lower bound $r\ge7.91$. 
@article{DM_2007_19_2_a11,
     author = {F. Yu. Vorob'ev},
     title = {A lower bound for the 4-satisfiability threshold},
     journal = {Diskretnaya Matematika},
     pages = {101--108},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_2_a11/}
}
TY  - JOUR
AU  - F. Yu. Vorob'ev
TI  - A lower bound for the 4-satisfiability threshold
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 101
EP  - 108
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_2_a11/
LA  - ru
ID  - DM_2007_19_2_a11
ER  - 
%0 Journal Article
%A F. Yu. Vorob'ev
%T A lower bound for the 4-satisfiability threshold
%J Diskretnaya Matematika
%D 2007
%P 101-108
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_2_a11/
%G ru
%F DM_2007_19_2_a11
F. Yu. Vorob'ev. A lower bound for the 4-satisfiability threshold. Diskretnaya Matematika, Tome 19 (2007) no. 2, pp. 101-108. http://geodesic.mathdoc.fr/item/DM_2007_19_2_a11/