Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке:
https://open.uns.ac.rs/handle/123456789/14182
Назив: | A sharp threshold for the hamilton cycle Maker-Breaker game | Аутори: | Hefetz D. Krivelevich M. Stojaković, Miloš Szabó T. |
Датум издавања: | 1-јан-2009 | Часопис: | Random Structures and Algorithms | Сажетак: | We study the Hamilton cycle Maker-Breaker game, played on the edges of the random graph G(n,p). We prove a conjecture from (Stojaković and Szabó, Random Struct and Algorithms 26 (2005), 204-223.), asserting that the property that Maker is able to win this game, has a sharp threshold at log n/n. Our theorem can be considered a game-theoretic strengthening of classical results from the theory of random graphs: not only does G(n,p) almost surely admit a Hamilton cycle for p = (1 + ε) log n/n, but Maker is able to build one while playing against an adversary. © 2008 Wiley Periodicals, Inc. | URI: | https://open.uns.ac.rs/handle/123456789/14182 | ISSN: | 10429832 | DOI: | 10.1002/rsa.20252 |
Налази се у колекцијама: | PMF Publikacije/Publications |
Приказати целокупан запис ставки
SCOPUSTM
Навођења
17
проверено 20.11.2023.
Преглед/и станица
8
Протекла недеља
7
7
Протекли месец
0
0
проверено 10.05.2024.
Google ScholarTM
Проверите
Алт метрика
Ставке на DSpace-у су заштићене ауторским правима, са свим правима задржаним, осим ако није другачије назначено.