Geodesic
A lower bound for the 4-satisfiability threshold
Diskretnaya Matematika, Tome 19 (2007) no. 2, pp. 101-108
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2007},
     volume = {19},
     number = {2},
     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
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
%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/

[1] Achlioptas D., Peres Y., “The threshold for random $k$-SAT is $2^k\ln2-O(k)$”, STOC, 2003, 223–231 | MR

[2] Friedgut E., “Necessary and sufficient conditions for sharp thresholds of graph properties, and the $k$-SAT problem”, J. Amer. Math. Soc., 12 (1999), 1017–1054 | DOI | MR | Zbl

[3] de Bruijn N. G., Asymptotic methods in analysis, Dover, New York, 1981 | MR | Zbl