The Erdős–Hajnal conjecture says that for any graph `H`, then every graph in the set of graphs `F_H` that does not contain `H` as an induced subgraph will eithe

The Erdős–Hajnal conjecture says that for any graph `H`, then every graph in the set of graphs `F_H` that does not contain `H` as an induced subgraph will either have a polynomial amount of cliques or a polymomial amount of independent sets. The growth rate of the exponent depends on the size of each graph in `F_H` and on some properties `H`. Like with most simple questions in Ramsay theory no proof or contradiction has been found for the general conjecture, but there has been some progress for some `H`. The latest paper proves that the conjecture is true if `H` is a cycle of 5 graphs. Since proving this was so hard and provided so much insight, there's hope that the general conjecture can be proved without a lot more work. ⠀ Here's an actual ELI5: There's a party where some pairs of guests know each other and some don't. A genie told you that there isn't any group of 5 people that only know two people from that group in a way that those relationships form a loop (1 — 2 — 3 — 4 — 5 — 1). Knowing that, you reason that this cannot be a regular party. Instead, it has to be one of these two: ⒈ A class reunion, where there's a large group of people that all know each other. ⒉ A group blind date, where there's a large group of people where nobody knows anyone. Being a smart 5-year-old the genie pushes you to publish a 19-page paper proving this, but you find out in Hacker News that some academics beat you and published it this February.