Geodesic
Using Lovász local lemma in the space of random injections
The electronic journal of combinatorics, Tome 14 (2007)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
The Lovász Local Lemma is known to have an extension for cases where independence is missing but negative dependencies are under control. We show that this is often the case for random injections, and we provide easy-to-check conditions for the non-trivial task of verifying a negative dependency graph for random injections. As an application, we prove existence results for hypergraph packing and Turán type extremal problems. A more surprising application is that tight asymptotic lower bounds can be obtained for asymptotic enumeration problems using the Lovász Local Lemma.
DOI : 10.37236/981
Classification : 05D40, 05A16, 60C05, 05C35, 05C70, 05C80
Mots-clés : dependency graph, negative dependency graph, Lovasz local lemma, random injections, permutation enumeration, hzpergraph packing, Turan-type extremal problems 
Linyuan Lu; László Székely. Using Lovász local lemma in the space of random injections. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/981
@article{10_37236_981,
     author = {Linyuan Lu and L\'aszl\'o Sz\'ekely},
     title = {Using {Lov\'asz} local lemma in the space of random injections},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/981},
     zbl = {1183.05088},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/981/}
}
TY  - JOUR
AU  - Linyuan Lu
AU  - László Székely
TI  - Using Lovász local lemma in the space of random injections
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/981/
DO  - 10.37236/981
ID  - 10_37236_981
ER  - 
%0 Journal Article
%A Linyuan Lu
%A László Székely
%T Using Lovász local lemma in the space of random injections
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/981/
%R 10.37236/981
%F 10_37236_981

Cité par Sources :