Threshold functions for extension statements (Q1812888): Difference between revisions

From author's introduction: Let \(H\) be a graph with vertices labelled \(x_ 1,\dots,x_ r\), \(y_ 1,\dots,y_ v\), where \(R=\{x_ 1,\dots,x_ r\}\) is a specified subset, called the roots. The pair \((R,H)\) will be dubbed a rooted graph. A graph \(G\) is said to satisfy the extension statement \(\hbox{Ext}(R,H)\) if for every choice of distinct \(x_ 1,\dots,x_ r\in V(G)\) there exist distinct \(y_ 1,\dots,y_ v\in V(G)\) such that \(\{x_ i,y_ j\}\in E(G)\) whenever \(\{x_ i,y_ j\}\in E(H)\) and \(\{y_ i,y_ j\}\in E(G)\) whenever \(\{y_ i,y_ j\}\in E(H)\). Let \(G=G(n,p)\) denote the random graph with \(n\) vertices and edge probability \(p\). Our concern will be to find the threshold functions for the statements \(\hbox{Ext}(R,H)\).