can I get an ELI5?
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.
I first understood the conjecture as bounding the exponential function on the size of the graph of an element of `F_H`, but apparently the odd thing is the exponent depends solely on `H`.
For your example where H forms a loop, I imagine an element of F_H which is a larger loop. Then it could be arbitrarily large, have no cliques above size 2, a linear number of cliques of size 2, and have only one independent set.
So in your loop example, you can take every other vertex in the loop and those form an independent set (of size n/2 ish). And n/2 is in Ω(n).
For understanding the conjecture itself, I think the mathematical description is the easier to comprehend than any analogy. See the intro of the Erdős–Hajnal conjecture Wikipedia article[1]. Graphs are pretty intuitive mathematical structures and the description of the conjecture only uses basic graph structures. Although maybe I'm just not clever enough to come up with a suitable analogy.
[1]: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Hajnal_conj...
It's not quite the same as complexity theory in computer science, but it's a pretty close analogy. Complexity theory doesn't necessarily have a lot of direct use, but it's certainly indirectly useful to engineering, and a very useful tool for an engineer to have in their toolbelt for measuring and talking about things that are otherwise too abstract to measure. Even if you aren't inclined to study it directly yourself, don't slag on it, because you benefit from the people who do.