Threshold functions for extension statements (Q1812888)

From MaRDI portal
Revision as of 01:31, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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