Avoiding small subgraphs in Achlioptas processes

DOI10.1002/RSA.20254MaRDI QIDQ3608317zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Po-Shen Loh, Benny Sudakov

Publication date 4 March 2009

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

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

zbMATH Keywords

thresholdrandom graphAchlioptas processsmall subgraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graph minors (05C83) Games involving graphs (91A43)

Abstract: For a fixed integer r, consider the following random process. At each round, one is presented with r random edges from the edge set of the complete graph on n vertices, and is asked to choose one of them. The selected edges are collected into a graph, which thus grows at the rate of one edge per round. This is a natural generalization of what is known in the literature as an Achlioptas process (the original version has r=2), which has been studied by many researchers, mainly in the context of delaying or accelerating the appearance of the giant component. In this paper, we investigate the small subgraph problem for Achlioptas processes. That is, given a fixed graph H, we study whether there is an online algorithm that substantially delays or accelerates a typical appearance of H, compared to its threshold of appearance in the random graph G(n, M). It is easy to see that one cannot accelerate the appearance of any fixed graph by more than the constant factor r, so we concentrate on the task of avoiding H. We determine thresholds for the avoidance of all cycles C_t, cliques K_t, and complete bipartite graphs K_{t,t}, in every Achlioptas process with parameter r >= 2.

Recommendations

• Small subgraphs in random graphs and the power of multiple choices
• Creating small subgraphs in Achlioptas processes with growing parameter
• The evolution of subcritical Achlioptas processes
• Hamiltonicity thresholds in Achlioptas processes
• Memoryless rules for Achlioptas processes

Cites work

• A phase transition for avoiding a giant component
• Avoiding a giant component
• Birth control for giants
• Compactness results in extremal graph theory
• Concentration of non‐Lipschitz functions and applications
• Creating a Giant Component
• Embracing the giant component
• Memoryless rules for Achlioptas processes
• Product rule wins a competitive game

Cited in

(19)

• Creating small subgraphs in Achlioptas processes with growing parameter
• Picker-chooser fixed graph games
• On balanced coloring games in random graphs
• Getting a directed Hamilton cycle two times faster
• Finding Hamilton cycles in random graphs with few queries
• Small subgraphs in random graphs and the power of multiple choices
• The Bohman-Frieze process near criticality
• Hamiltonicity thresholds in Achlioptas processes
• Random \(k\)-SAT and the power of two choices
• Ramsey games with giants
• Delaying satisfiability for random 2SAT
• A geometric Achlioptas process
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• On balanced coloring games in random graphs
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• On the power of choice for Boolean functions
• Offline thresholds for Ramsey-type games on random graphs
• Memoryless rules for Achlioptas processes
• Probabilistic intuition holds for a class of small subgraph games

This page was built for publication: Avoiding small subgraphs in Achlioptas processes

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