Avoiding small subgraphs in Achlioptas processes

DOI10.1002/RSA.20254MaRDI QIDQ3608317zbMATHOpenAlexFDO

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)

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