Mathematicians Settle Erdős Coloring Conjecture(quantamagazine.org)
quantamagazine.org
Mathematicians Settle Erdős Coloring Conjecture
https://www.quantamagazine.org/mathematicians-settle-erdos-coloring-conjecture-20210405/
18 comments
> Now, if they have a bound on n, or if it's possible to derive a bound from their proof, then this could eventually become a proof of the full conjecture, by computer checking all smaller n. But if it's nonconstructive, then it can't be.
Actually, if they could somehow embed the small hypergraphs into the large ones so that the coloring on the small ones is the same, they could prove it completely. I wonder why is this not the case, but I suspect they are gonna do it, see:
“There is still the assumption in the paper that the number of nodes must be very large, but that’s probably just some additional work,” said Lovász. “Essentially, the conjecture is now proved.”
Actually, if they could somehow embed the small hypergraphs into the large ones so that the coloring on the small ones is the same, they could prove it completely. I wonder why is this not the case, but I suspect they are gonna do it, see:
“There is still the assumption in the paper that the number of nodes must be very large, but that’s probably just some additional work,” said Lovász. “Essentially, the conjecture is now proved.”
It does say this at the end of the article.
> Because of the probabilistic elements, their proof only works for large enough hypergraphs — those with more than a specific number of vertices. This approach is common in combinatorics, and mathematicians consider it a nearly complete proof since it only omits a finite number of hypergraphs.
> Because of the probabilistic elements, their proof only works for large enough hypergraphs — those with more than a specific number of vertices. This approach is common in combinatorics, and mathematicians consider it a nearly complete proof since it only omits a finite number of hypergraphs.
Ah, I missed that, thanks. That said, I think there's still a big difference between "only omits a finite number of hypergraphs" and "only omits a finite number of hypergraphs of bounded size". I'd regard the latter as nearly a complete proof, not so much the former. (E.g., I don't think anyone would say that we have a nearly complete proof of Artin's primitive root conjecture.) Now, it sounds like this is the latter in the sense that it can be made so, but it also sounds like it's not explicitly the latter and someone needs to actually still do that work.
There is not a big difference between those two statements. In fact they are identical in meaning.
There is a subtle but important difference. To be more precise, consider the following two statements:
1) There exists some n such that all integers >= n satisfy the desired property.
2) For n = [a specific constant], all integers >= n satisfy the desired property.
These two statements are not the same, but both imply that there are a finite number of counterexamples. The second one is stronger, since we could prove the statement by enumerating all k < n and checking the statement for each such k; if all these checks pass, then the statement is correct.
This strategy does not work for the first strategy since we do not know n, only that such an n exists. In particular, there could be a non-constructive proof that establishes existence of such an n without providing any way to compute such an n.
From the discussion, it does sound like this paper is proving (2), not (1).
1) There exists some n such that all integers >= n satisfy the desired property.
2) For n = [a specific constant], all integers >= n satisfy the desired property.
These two statements are not the same, but both imply that there are a finite number of counterexamples. The second one is stronger, since we could prove the statement by enumerating all k < n and checking the statement for each such k; if all these checks pass, then the statement is correct.
This strategy does not work for the first strategy since we do not know n, only that such an n exists. In particular, there could be a non-constructive proof that establishes existence of such an n without providing any way to compute such an n.
From the discussion, it does sound like this paper is proving (2), not (1).
Yup. You came in and said it before I could get back to this...
For any n, there are only a finite number of hypergraphs on n vertices, much less linear hypergraphs. It is therefore correct, and equivalent to say that the proof omits "only a finite number of hypergraphs," when the result is shown for sufficiently large n. I haven't read the paper through, but, I suspect it's even possible to extract some explicit value of n for which the conjecture is true. In any case, it's enough to know that there is such an n.
I looked up Artin's primitive root conjecture on Wiki because I wasn't familiar with the result. I think you may be referencing the result that there are at most 2 primes for which the conjecture fails, no? If so, I would agree that's not close to a complete proof.
The difference here is that, in principle, since hypergraphs are just finite combinatorial objects, one could, in theory just run a generic coloring algorithm over the finite number of things left out of the proof to obtain the complete result with a bow tied around it.
In the case of Artin's conjecture, you have two difficulties: identifying 1 or 2 candidate primes for which it may fail, and verifying the conjecture for those primes. Even if you can somehow overcome the first difficulty and identify the candidate primes for which it may fail, in the absence of machinery that lets us make such a conclusion for those two primes, we are reduced to calculating an infinite number of discrete logarithms, which, obviously doesn't fly.
So, TL;DR: the difference here is literally the difference between finite and infinite. There are a finite number of hypergraphs left out, which can, in theory be tested using a finite number of operations to verify the conjecture. Not so with Artin's conjecture.
https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primit...
I looked up Artin's primitive root conjecture on Wiki because I wasn't familiar with the result. I think you may be referencing the result that there are at most 2 primes for which the conjecture fails, no? If so, I would agree that's not close to a complete proof.
The difference here is that, in principle, since hypergraphs are just finite combinatorial objects, one could, in theory just run a generic coloring algorithm over the finite number of things left out of the proof to obtain the complete result with a bow tied around it.
In the case of Artin's conjecture, you have two difficulties: identifying 1 or 2 candidate primes for which it may fail, and verifying the conjecture for those primes. Even if you can somehow overcome the first difficulty and identify the candidate primes for which it may fail, in the absence of machinery that lets us make such a conclusion for those two primes, we are reduced to calculating an infinite number of discrete logarithms, which, obviously doesn't fly.
So, TL;DR: the difference here is literally the difference between finite and infinite. There are a finite number of hypergraphs left out, which can, in theory be tested using a finite number of operations to verify the conjecture. Not so with Artin's conjecture.
https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primit...
I don't think that's quite right. There are two possible precise statements for such claims:
1) There exists some n such that all integers >= n satisfy the desired property.
2) For n = [a specific constant], all integers >= n satisfy the desired property.
I'm not familiar with Artin's conjecture, but from your description, it satisfies (1) but not (2). The reason is that if there are at most 2 such primes, we can take n to be the larger of the two primes plus one. Since all primes are finite, this choice of n is also finite.
I think the key question is whether the paper described in this article proves (1) or (2). From the discussion, it sounds like it proves (2), which is the stronger result.
1) There exists some n such that all integers >= n satisfy the desired property.
2) For n = [a specific constant], all integers >= n satisfy the desired property.
I'm not familiar with Artin's conjecture, but from your description, it satisfies (1) but not (2). The reason is that if there are at most 2 such primes, we can take n to be the larger of the two primes plus one. Since all primes are finite, this choice of n is also finite.
I think the key question is whether the paper described in this article proves (1) or (2). From the discussion, it sounds like it proves (2), which is the stronger result.
Yup, you came in and said it before I could. Knowing how many counterexamples there could be doesn't help very much if you don't have any bound on their size. pmiller2 seems to assume that there is some way to identify the two candidates, but the problem is that there isn't; the proof is nonconstructive. Nonconstructive proofs are a thing, and it's often important to distinguish whether a given existence proof is constructive or not.
Can someone ELI5 the real world applications of this? I don't know many people who spend their time coloring graphs, let alone needing to know how many colors are needed to color them.
Graph colouring is NP-Complete, and many real world problems map fairly naturally to it. I wrote a program that factors integers by colouring graphs as a demonstrator, but it's easy enough to use colouring to solve SAT problems.
In compiler technology, "register colouring" is a thing, although no longer necessarily the best technique to solve the particular problem. Optimal Route Computation can be cast as a graph colouring problem, as can scheduling.
I recorded a talk about this some time ago in which I proved that G3C (Graph 3-Colouring) is NPC, let me know if you'd like a link and I'll see if it's still available. If not, I'm giving it again as a part of the G4G Celebration of Mind series of talks.
In compiler technology, "register colouring" is a thing, although no longer necessarily the best technique to solve the particular problem. Optimal Route Computation can be cast as a graph colouring problem, as can scheduling.
I recorded a talk about this some time ago in which I proved that G3C (Graph 3-Colouring) is NPC, let me know if you'd like a link and I'll see if it's still available. If not, I'm giving it again as a part of the G4G Celebration of Mind series of talks.
Math doesn't necessarily consider the real world applications. That said you can represent almost anything as a graph, and "how many different x will we need for y" is a fairly common question. This provides the answer for certain kinds of y.
Many problems can be reduced to graph coloring problems if you look at it the right way. Try understanding the standard examples (see the applications section in Wikipedia), then it is really easy to come up with your own applications.
graphs are used all the time in programming. knowing more about them could prove useful to someone sometime. Also may never be useful.
[deleted]
I love the picture of their notes! [1] It hints of iteration and exploration (multiple drawings of flower-petal-looking graphs), corrections (scribbled over symbols), refinement ("Phase J" appears in multiple places), and, above all, collaboration (different colors!). A great representation of the process of mathematical discovery.
It's so different from the austere presentation of a polished LaTeX paper. A completed proof leaves out so much of the exploration process -- the doodling, hopeful symbol-pushing, flawed intermediate conjectures and conclusions -- and just leaves an artificially linear representation of how to approach the problem. It's easy to feel despair when a textbook or paper presents something so succinctly, as if it's the most obvious thing in the world, but there was a lot of stumbling around in darkness (the dark background of the note-taking software!) before the elegant formulation was finally illuminated.
Graph problems and combinatoric problems are especially fun to puzzle out in a notebook as it's especially easy to come up with examples, though it does get difficult to play around with larger graphs. Recently I tried to find an algorithm for generating round-robin tournament pairings, and ended up filling pages of notes with tables and dissections of complete graphs. It's a fun challenge, and accessible even to someone without a theoretical math background. I eventually found a horrendously complicated solution, one I was proud of, even after reading a supremely simple construction on Wikipedia.
[1] https://d2r55xnwy6nx47.cloudfront.net/uploads/2021/04/Zoom-S...
It's so different from the austere presentation of a polished LaTeX paper. A completed proof leaves out so much of the exploration process -- the doodling, hopeful symbol-pushing, flawed intermediate conjectures and conclusions -- and just leaves an artificially linear representation of how to approach the problem. It's easy to feel despair when a textbook or paper presents something so succinctly, as if it's the most obvious thing in the world, but there was a lot of stumbling around in darkness (the dark background of the note-taking software!) before the elegant formulation was finally illuminated.
Graph problems and combinatoric problems are especially fun to puzzle out in a notebook as it's especially easy to come up with examples, though it does get difficult to play around with larger graphs. Recently I tried to find an algorithm for generating round-robin tournament pairings, and ended up filling pages of notes with tables and dissections of complete graphs. It's a fun challenge, and accessible even to someone without a theoretical math background. I eventually found a horrendously complicated solution, one I was proud of, even after reading a supremely simple construction on Wikipedia.
[1] https://d2r55xnwy6nx47.cloudfront.net/uploads/2021/04/Zoom-S...
With Ron Graham's passing, does anyone know what becomes of the famous Erdos checks? I know there's no monetary value to them but I would bet many people would just frame them to display it like a badge of honor.
Now, if they have a bound on n, or if it's possible to derive a bound from their proof, then this could eventually become a proof of the full conjecture, by computer checking all smaller n. But if it's nonconstructive, then it can't be. To be clear, this is still an interesting and impressive result either way! But let's make sure we've correctly stated just what it is.
From the description in the article, it sounds like it ought to be possible to derive a bound on n from their proof. But from what I've seen, it doesn't sound like they've done so. So, now some proof-miner will have to go and do that for them, I guess, and possibly prove the full conjecture as a result...