Mathematicians submit proof of Erdős Coloring Conjecture

Fifty years ago, several mathematicians at a dinner party were discussing graphs (points and lines, not chart graphs), and the generalization if you make the edges connecting a point (vertex) with another, able to connect multiple points. While working out the minimal number of colors in general, they found it to be an interesting problem, to test out and prove the next day… Well, that solution, to Erdős, Faber, and Lovász’ problem was delayed for years and years!

The proof (for high number of vertices) hinges upon having three especially colorful examples as shown in the article here… and finding that those that are significantly from these have less, not more colors required for coloring them.

The Wikipedia article links a real life explanation of that “linear hypergraph” with at most one common one for any two different hypergraph “edges” (more of a glob than a line in the examples you see in the article.): “n committees each with n members each, such that each pair of committees has at most one member in common”. If that is easier to understand than the article. It’s interesting to see that the proof calls it a proof for “every large n” – so it may be worthwhile looking at smaller graphs for a counterexample, interestingly enough!?

It is interesting to see this was split in to different highly-colorized groups and then from there found that the ones similar were ones with fewer colors. Similarly, the old Four-color theorem was reduced to a set of thousands of reducible states which were proved by computer over many hours.

It is ironic that the problem conceived 50 years ago at a tea party had a key part solved in the height of a pandemic… For the near future it is not likely that we will have many math dinner parties which is unfortunate, but at least that might mean less new tricky problems that would keep the mathematicians more busy for years to come?

Leave a Reply

Your email address will not be published. Required fields are marked *

+ thirty seven = thirty nine