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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Consider the following random process: The vertices of a binomial random graph  G   n,p   are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number  r  of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph  F  in the process. Our first main result is that for any  F  and  r , the threshold function for this problem is given by  p  0 ( F,r,n ) =  n  ‐1 / m*  1 ( F,r ), where  m*  1 ( F,r ) denotes the so‐called  online vertex‐Ramsey density  of  F  and  r . This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any  F  and  r , the online vertex‐Ramsey density m* 1 ( F,r ) is a computable rational number.  Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring  G   n,p   as desired with probability 1 ‐  o (1) for any  p ( n ) =  o ( n  ‐1 / m*  1 ( F,r )). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014

Coloring random graphs online without creating monochromatic subgraphs