Constrainted graph processes
type: Item
instance of: scholarly article
title: Constrainted graph processes
zbMATH Open document ID: 0939.05074
author: Béla Bollobás
author: Oliver Riordan
published in: The Electronic Journal of Combinatorics
publication date: 2000-04-16T00:00:00Z
full work available at URL: https://eudml.org/doc/120358
full work available at URL: v7i1r18.html
review text: Summary: Let \(\mathcal Q\) be a monotone decreasing property of graphs \(G\) on \(n\) vertices. \textit{P. Erdős, S. Suen} and \textit{P. Winkler} [Random Struct. Algorithms 6, No. 2-3, 309-318 (1995; Zbl 0820.05054)]\ introduced the following natural way of choosing a random maximal graph in \(\mathcal Q\): start with \(G\) the empty graph on \(n\) vertices. Add edges to \(G\) one at a time, each time choosing uniformly from all \(e\in G^c\) such that \(G+e\in \mathcal Q\). Stop when there are no such edges, so the graph \(G_\infty\) reached is maximal in \(\mathcal Q\). Erdős, Suen and Winkler asked how many edges the resulting graph typically has, giving good bounds for \(\mathcal Q=\) \{bipartite graphs\} and \(\mathcal Q=\) \{triangle free graphs\}. We answer this question for \(C_4\)-free graphs and for \(K_4\)-free graphs, by considering a related question about standard random graphs \(G_p\in \mathcal G(n,p)\). The main technique we use is the `step by step' approach of our paper [(*) Colorings generated by monotone properties, Random Struct. Algorithms 12, No. 1, 1-25 (1998; Zbl 0894.05043)]. We wish to show that \(G_p\) has a certain property with high probability. For example, for \(K_4\)-free graphs the property is that every `large' set \(V\) of vertices contains a triangle not sharing an edge with any \(K_4\) in \(G_p\). We would like to apply a standard Martingale inequality, but the complicated dependence involved is not of the right form. Instead we examine \(G_p\) one step at a time in such a way that the dependence on what has gone before can be split into `positive' and `negative' parts, using the notions of up-sets and down-sets. The relatively simple positive part is then estimated directly. The much more complicated negative part can simply be ignored, as shown in (*).
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 1431769
zbMATH Keywords: random graphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1431769