Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/14182
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hefetz D. | en_US |
dc.contributor.author | Krivelevich M. | en_US |
dc.contributor.author | Stojaković, Miloš | en_US |
dc.contributor.author | Szabó T. | en_US |
dc.date.accessioned | 2020-03-03T14:55:16Z | - |
dc.date.available | 2020-03-03T14:55:16Z | - |
dc.date.issued | 2009-01-01 | - |
dc.identifier.issn | 10429832 | en_US |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/14182 | - |
dc.description.abstract | 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. | en |
dc.relation.ispartof | Random Structures and Algorithms | en |
dc.title | A sharp threshold for the hamilton cycle Maker-Breaker game | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.doi | 10.1002/rsa.20252 | - |
dc.identifier.scopus | 2-s2.0-60349097895 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/60349097895 | - |
dc.description.version | Unknown | en_US |
dc.relation.lastpage | 122 | en |
dc.relation.firstpage | 112 | en |
dc.relation.issue | 1 | en |
dc.relation.volume | 34 | en |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.orcid | 0000-0002-2545-8849 | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
Appears in Collections: | PMF Publikacije/Publications |
SCOPUSTM
Citations
17
checked on Nov 20, 2023
Page view(s)
8
Last Week
7
7
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.