Geodesic
Biased positional games and small hypergraphs with large covers
The electronic journal of combinatorics, Tome 15 (2008)

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

Zbl EuDML
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 
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
@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

Cité par Sources :