Mathematicians have recently “proven” the Erdős-Faber-Lovász coloring conjecture. I put “proven” in quotes because the proof only works for “large enough” hypergraphs, a restriction that I think is rather cavalierly addressed in the linked article. Nevertheless, it would be interesting to consider whether some of the techniques used in the proof could be adapted for general constraint satisfaction problem solving. At least one technique they use seems already to be related to a CP staple: “hardest first (fail first)” ordering; perhaps some readers can identify others. Even more interesting would be if some of the methods used in the proof suggest new CP techniques. And it would be exciting if any existing CP techniques suggest alternative or improved proofs of the conjecture.
Erdős-Faber-Lovász
Leave a reply
