Threshold functions for extension statements
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)\).
- Matching and covering the vertices of a random graph by copies of a given graph
- On the number of \(r\)-transitive orientations of \(G(n,p)\)
- First order sentences about random graphs: small number of alternations
- Quantifier alternation in first-order formulas with infinite spectra
- Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
- Infinite spectra of first-order properties for random hypergraphs
- Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations
- Counting extensions
- Bounded quantifier depth spectra for random graphs
- Threshold Functions for H-factors
- Short monadic second order sentences about sparse random graphs
- Small subgraphs and their extensions in a random distance graph
- First-order properties of bounded quantifier depth of very sparse random graphs
- Counting restricted orientations of random graphs
- The reverse \(H\)-free process for strictly 2-balanced graphs
- On fractional K‐factors of random graphs
- Counting extensions revisited
- Weak saturation stability
- Weakly saturated subgraphs of random graphs
- Cycle Saturation in Random Graphs
- Threshold for stability of weak saturation
- Maximum number of symmetric extensions in random graphs
- Weak saturation numbers in random graphs
- On the spectra of first-order language properties for random graphs
This page was built for publication: Threshold functions for extension statements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1812888)
