Threshold functions for extension statements (Q1812888)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Threshold functions for extension statements
scientific article

    Statements

    Threshold functions for extension statements (English)
    0 references
    25 June 1992
    0 references
    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)\).
    0 references
    0 references
    graph extensions
    0 references
    random graph
    0 references
    threshold functions
    0 references
    0 references