Geodesic
On the size of minimal unsatisfiable formulas
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

An unsatisfiable formula is called minimal if it becomes satisfiable whenever any of its clauses are removed. We construct minimal unsatisfiable $k$-SAT formulas with $\Omega(n^k)$ clauses for $k \geq 3$, thereby negatively answering a question of Rosenfeld. This should be compared to the result of Lovász [Studia Scientiarum Mathematicarum Hungarica 11, 1974, p113-114] which asserts that a critically 3-chromatic $k$-uniform hypergraph can have at most ${n\choose k-1}$ edges.
DOI : 10.37236/241
Classification : 68Q25, 68R10, 68T20, 05C65, 05C15, 05C35
Mots-clés : minimal unsatisfiable formulas, critically 3-connected hypergraphs 
@article{10_37236_241,
     author = {Choongbum Lee},
     title = {On the size of minimal unsatisfiable formulas},
     journal = {The electronic journal of combinatorics},
     year = {2009},
     volume = {16},
     number = {1},
     doi = {10.37236/241},
     zbl = {1178.68290},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/241/}
}
TY  - JOUR
AU  - Choongbum Lee
TI  - On the size of minimal unsatisfiable formulas
JO  - The electronic journal of combinatorics
PY  - 2009
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/241/
DO  - 10.37236/241
ID  - 10_37236_241
ER  - 
%0 Journal Article
%A Choongbum Lee
%T On the size of minimal unsatisfiable formulas
%J The electronic journal of combinatorics
%D 2009
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/241/
%R 10.37236/241
%F 10_37236_241
Choongbum Lee. On the size of minimal unsatisfiable formulas. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/241

Cité par Sources :