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

Achlioptas processrandom graphsmall subgraphthreshold

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83) Combinatorial probability (60C05) 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

(20)

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

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)