Geodesic
Biased positional games and small hypergraphs with large covers
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove that in the biased $(1:b)$ Hamiltonicity and $k$-connectivity Maker-Breaker games ($k>0$ is a constant), played on the edges of the complete graph $K_n$, Maker has a winning strategy for $b\le(\log 2-o(1))n/\log n$. Also, in the biased $(1:b)$ Avoider-Enforcer game played on $E(K_n)$, Enforcer can force Avoider to create a Hamilton cycle when $b\le (1-o(1))n/\log n$. These results are proved using a new approach, relying on the existence of hypergraphs with few edges and large covering number.
DOI : 10.37236/794
Classification : 91A43, 91A46, 05C65 
@article{10_37236_794,
     author = {Michael Krivelevich and Tibor Szab\'o},
     title = {Biased positional games and small hypergraphs with large covers},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/794},
     zbl = {1160.91007},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/794/}
}
TY  - JOUR
AU  - Michael Krivelevich
AU  - Tibor Szabó
TI  - Biased positional games and small hypergraphs with large covers
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/794/
DO  - 10.37236/794
ID  - 10_37236_794
ER  - 
%0 Journal Article
%A Michael Krivelevich
%A Tibor Szabó
%T Biased positional games and small hypergraphs with large covers
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/794/
%R 10.37236/794
%F 10_37236_794
Michael Krivelevich; Tibor Szabó. Biased positional games and small hypergraphs with large covers. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/794

Cité par Sources :