Avoiding small subgraphs in Achlioptas processes

DOI10.1002/RSA.20254zbMATH Open1182.05112arXiv0708.0443OpenAlexW2951119921MaRDI QIDQ3608317FDOQ3608317

Benny Sudakov, Michael Krivelevich, Po-Shen Loh

Publication date: 4 March 2009

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

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.

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)

Cites Work

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

Cited In (17)

• 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
• On the Power of Choice for Boolean Functions
• Ramsey games with giants
• Delaying satisfiability for random 2SAT
• A geometric Achlioptas process
• Random k -SAT and the power of two choices
• 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
• Offline thresholds for Ramsey-type games on random graphs
• 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)