A graph property is a condition on graphs that is invariant under graph isomorphism. For simple
graphs on a fixed vertex set 
, it can be represented by a family 
of subsets
of the possible edges, invariant
under every permutation of 
(Friedgut and Kalai 1996). For example, being a connected
graph, a bipartite graph, or a Hamiltonian
graph is a graph property.
A graph property is increasing if adding edges preserves membership in 
.
Connectivity and the presence of a Hamiltonian cycle
are increasing graph properties. An increasing graph property is nontrivial if 
is neither the empty
set nor the entire space of graphs under consideration.
In the random graph 
, each possible edge on
vertices
is present independently with probability 
. The location of the transition for containing a prescribed
graph is related to the graph
expectation threshold. The Friedgut-Kalai
sharp-threshold conjecture concerns the width of the transition for arbitrary
nontrivial increasing graph properties.
