Threshold functions for extension statements
Joel Spencer · Journal of Combinatorial Theory Series A · 1990
Let H be a graph with vertices labelled .Y,, . . . .x,, y,, . . . .y,, where R = (x xr} is a specified subset, called the roots.The pair (R, If) will be dubbed a rooted graph.A graph G is said to satisfy the extension statement Ext(R, H) if for every choice of distinct x1, . . . .X,E V(G) there exist distinct y,, . ., JJ~} E E(H) and (yi, v,] EE(G) whenever {y,, y,', GE(H).EXAMPLES.(i) No vertex is isolated.(H an edge on x,, v,.) (ii) Every vertex lies in a triangle.(H a triangle on x1, .P,, yz.) (iii) Every pair of points lie on a path of length d. (H a path of length d with R the two endpoints.)