Erdős–Hajnal conjecture
In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal. More precisely, for an arbitrary undirected graph formula_1, let formula_2 be the family of graphs that do not have formula_1 as an induced subgraph. Then, according to the conjecture, there exists a constant formula_4 such that the formula_5-vertex graphs in formula_2 have either a clique or an independent set of size formula_7. An equivalent statement to the original  conjecture is that, for every graph formula_1, the formula_1-free graphs all contain polynomially large perfect induced subgraphs. Graphs without large cliques or independent sets. In contrast, for random graphs in the Erdős–Rényi model with edge probability 1/2, both the maximum clique and the maximum independent set are much smaller: their size is proportional to the logarithm of formula_5, rather than growing polynomially. Ramsey's theorem proves that no graph has both its maximum clique size and maximum independent set size smaller than logarithmic. Ramsey's theorem also implies the special case of the Erdős–Hajnal conjecture when formula_1  itself is a clique or independent set. Partial results. This conjecture is due to Paul Erdős and András Hajnal, who proved it to be true when formula_1 is a cograph. They also showed, for arbitrary formula_1, that the size of the largest clique or independent set grows superlogarithmically. More precisely, for every formula_1 there is a constant formula_15 such that the formula_5-vertex formula_1-free graphs have cliques or independent sets containing at least formula_18 vertices. The graphs formula_1 for which the conjecture is true also include those with four verticies or less, all five-vertex graphs except the five -vertex path and its complement, and any graph that can be obtained from these and the cographs by modular decomposition. As of 2021, however, the full conjecture has not been proven, and remains an open problem. An earlier formulation of the conjecture, also by Erdős and Hajnal, concerns the special case when formula_1 is a 5-vertex cycle graph. This case has been resolved by Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl in 2021. The formula_21-free graphs include the perfect graphs, which necessarily have either a clique or independent set of size proportional to the square root  of their number of vertices. Conversely, every clique or independent set is itself perfect. For this reason, a convenient and symmetric reformulation of the Erdős–Hajnal conjecture is that for every graph formula_1, the formula_1-free graphs necessarily contain an induced perfect subgraph of polynomial size. Relation to the chromatic number of tournaments. Alon et al. showed that the following statement concerning tournaments is equivalent to the Erdős-Hajnal conjecture. Here formula_31 denotes the chromatic number of formula_28, which is the smallest formula_33 such that there is a formula_34-coloring for formula_28. A coloring of a tournament formula_28 is a  mapping formula_37 such that the color classes formula_38 are transitive for all formula_39. The class of tournaments formula_1 with the property that every formula_1-free tournament formula_28 has formula_43 for some constant formula_44 satisfies this equivalent Erdős-Hajnal conjecture (with formula_45). Such tournaments formula_1, called heroes, were considered by Berger et al. There it is proven that a hero has a special structure which is as follows: Here formula_47 denotes the tournament with the three components formula_1, the transitive tournament of size formula_34 and a single node formula_54. The arcs between the three components are defined as follows: formula_55. The  tournament formula_48 is defined analogously.