Coloring random graphs online without creating monochromatic subgraphs

DOI10.1002/RSA.20445MaRDI QIDQ5495876zbMATH OpenOpenAlexFDO

Authors Torsten Mütze, Thomas Rast, Reto Spöhel

Publication date 7 August 2014

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.5849

zbMATH Keywords

random graphRamsey propertyonline process

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Abstract: 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^{\ast }(F,r)}$, where $m_1^{\ast }(F,r)$ denotes the so-called emph{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^{\ast }(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^{\ast }(F,r)})$.

Recommendations

• Coloring random graphs online without creating monochromatic subgraphs
• scientific article; zbMATH DE number 6381676
• Online vertex-coloring games in random graphs
• Online Ramsey games in random graphs
• Balanced online Ramsey games in random graphs

Cites work

• Coloring random graphs online without creating monochromatic subgraphs
• Equitable coloring of random graphs
• Globally sparse vertex‐ramsey graphs
• Hunting for sharp thresholds
• On the path-avoidance vertex-coloring game
• On the strong chromatic number of random graphs
• On-line Ramsey Numbers
• On-line Ramsey numbers for paths and stars
• On-line Ramsey theory
• On-line Ramsey theory for bounded degree graphs
• Online Ramsey games for triangles in random graphs
• Online Ramsey games in random graphs
• Online vertex-coloring games in random graphs
• Probabilistic One-Player Ramsey Games via Deterministic Two-Player Games
• Ramsey Games Against a One-Armed Bandit
• Ramsey properties of random graphs
• Sharp thresholds for certain Ramsey properties of random graphs
• The \(t\)-improper chromatic number of random graphs
• There is no fast method for finding monochromatic complete subgraphs
• Threshold functions for small subgraphs
• Two variants of the size Ramsey number
• Upper bounds for online Ramsey games in random graphs

Cited in

(4)

• Proper colouring painter-builder game
• Tight bounds for online vector scheduling
• Coloring random graphs online without creating monochromatic subgraphs
• Randomized online graph coloring

This page was built for publication: Coloring random graphs online without creating monochromatic subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495876)