Almost All F-Free Graphs Have The Erdos-Hajnal Property
Résumé
Erdős and Hajnal conjectured that, for every graph H, there exists a constant ɛ(H) > 0 such that every H-free graph G (that is, not containing H as an induced subgraph) must contain a clique or an independent set of size at least |G|ɛ( H). We prove that there exists ɛ(H) such that almost every H-ïvee graph G has this property, meaning that, amongst the if-free graphs with n vertices, the proportion having the property tends to one as n → ∞.