English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study biased Maker-Breaker positional games between two players, one ofwhom is playing randomly against an opponent with an optimal strategy. In thispaper we consider the scenario when Maker plays randomly and Breaker is"clever", and determine the sharp threshold bias of classical graph games, suchas connectivity, Hamiltonicity, and minimum degree-$k$. We treat the othercase, that is when Breaker plays randomly, in a separate paper. Thetraditional, deterministic version of these games, with two optimal playersplaying, are known to obey the so-called probabilistic intuition. That is, thethreshold bias of these games is asymptotically equal to the threshold bias oftheir random counterpart, where players just take edges uniformly at random. Wefind, that despite this remarkably precise agreement of the results of thedeterministic and the random games, playing randomly against an optimalopponent is not a good idea: the threshold bias becomes significantly moretilted towards the random player. An important qualitative aspect of theprobabilistic intuition carries through nevertheless: the bottleneck for Makerto occupy a connected graph is still the ability to avoid isolated vertices inher graph.

Sharp thresholds for half-random games I