4 ms·

k-Coloring is Faster than Computing the Chromatic Number

74 points by matt_d 3mo ago

black_knight 2mo ago
At the end of brev paper there is a section on the LLM usage. Now, this paper will undergo peer review. And thus, when published, we will trust the result as well as any other published result in mathematics. However, while humans are not infallible, LLMs have a tendency to spit out confident stuff which looks correct. Thus I worry when it is used this way to produce proofs. Peer review is not perfect, and may not be tuned to catch LLM’s style of errors. There is a solution to this, which is to formalise the result and get it machine verified. And with LLMs, I daresay this is going to be best practice moving forward.
- appplication 2mo ago
  > Peer review is not perfect, and may not be tuned to catch LLM’s style of errors This summarizes I think a lot of the challenges with validating LLM output. We hear “humans make mistakes too”, but I would agree with you that our human detection of human-made mistakes and LLM-made mistakes is unlikely to have the same coverage.
  - airstrike 2mo ago
    The real problem is that human mistakes generally occur more frequently given the difficulty of the task, whereas LLM mistakes are somewhat random, like the carwash problem, because LLMs cannot truly reason. I'd rather have a human on my team for whom I can reasonably surmise what tasks they're good at than have a robot who randomly gets shit wrong.
    - yndoendo 2mo ago
      I worded a questions similar to this with a person in the finance industry. He was very receptive of AI since it is one of the easiest ways to grow stock portfolio. Say you have two assistant employees. One that reads the reports and one that uses AI to summarize the content. You are sitting in a high value meeting. You only can have one assistant with you in the meeting. Which one would you pick, the persons that read the reports or the person who only used AI?
      - aleph_minus_one 2mo ago
        > Say you have two assistant employees. One that reads the reports and one that uses AI to summarize the content. You are sitting in a high value meeting. You only can have one assistant with you in the meeting. Which one would you pick, the persons that read the reports or the person who only used AI? I would take the person who only used AI. Why? Your fictional problem has the silent assumption that if you are in a high value meeting, you shall act more conservatively (i.e. reduce risk for reliability, even if you loose chances/opportunities). But this is rather a statement that the respective person acts on a risk-averse profile. I rather have a risk-affine profile. Because it is likely that everybody else in the meeting has a risk-averse profile, it is very likely that if I act on the "non-conservative" choice and I am right, I will have a huge advantage. On the other hand, if I act on the conservative choice, I won't have any advantage over the other participants. Since I am risk-affine person, I am willing to risk it. :-)
        yndoendo 2mo ago
        There was no time frame from reading the report and AI summary to having to apply the report is stated. It could be one hour to 30 days in between or more. There was no statement if the meeting was scheduled or impromptu. Client(s) might have saw you in public or at an event. Or at a trade show and there the report only applies to the single client versus to many clients. There was no statement of report ownership. All parties might have access to it. There is a chance that AI lied / hallucinated the summary. Only to know would be taking time to read the report and validate it. AI only consumption has shown to reduce retention of information compared to reading the core content. Ever have someone tell you why they want AI? I have, it was because they do not want to read the reports.
    - gus_massa 2mo ago
      > whereas LLM mistakes are somewhat random, like the carwash problem At least in math problems, AI mistakes generally occur more frequently given the difficulty of the task. The carwash problem is very undespecified. The question should be something like "I am American. I live in a single family home in a suburb. Each member of my family has their own car. All the cars are parked during the night at home. My boss don't authorize me to go during working hour outside the office. I want to wash my car. The car wash is 50 meters away. Should I walk or drive?" Disclaimer: I am Argentinean. I live in an old apartment building without a parking lot. I don't have a car, but if I had one I'd probably move to a building with parking inside or nearby. The closest professional car washing facility is like 1000 meters away, but the closest parking lot is like 50 meters away and they guys would wash the car for a few bucks. I want to wash my car. The car wash is 50 meters away. Should I walk or drive?
      - airstrike 2mo ago
        You're picking on the specifics of the carwash problem rather than acknowledging countless other similar problems exist. The original one was strawberry, but that got RL'd away
        gus_massa 2mo ago
        The strawberry problem is a translation/encoding problem, not a context problem. To be more efficient and cheap, the implementations use tokens, that is very-slightly-similar to translate it to Japanese: イチゴには「r」がいくつありますか？ (I don't speak Japanese, I used autotranslation, so it may be wrong.) There are no "r" in the token of strawberry.
        airstrike 2mo ago
        And yet, if models could indeed reason, that would not be an issue. You're arguing my point.
emil-lp 2mo ago
For those not familiar: K-Coloring is the property that a graph can be colored with k colors such that no two neighboring nodes get the same color. The K-Coloring problem is a decision problem, ie a yes/no question. The chromatic number of a graph is the lowest k for which it has a k-coloring. Clearly, if you have an algorithm for one, you have an algorithm for the other. The question was: is it faster to compute k-coloring than to compute its lowest (actual) k, ie its chromatic number. Forests, trees, and bipartite graphs are 2-colorable. Planar graphs are 4-colorable. It is NP-complete to check if the chromatic number of a planar graph is 3. There's a very interesting open problem, Hadwiger's conjecture that essentially says that the chromatic number is the clique (minor) number (whatever that means).
- aleph_minus_one 2mo ago
  > Forests, trees, and bipartite graphs are 2-colorable. More precise: a graph is bipartite if and only if it is 2-colorable (this can actually be used as a definition). Since forests are bipartite, and trees are forests, the other two statements follow.
  - emil-lp 2mo ago
    Precisely! The reason I mentioned trees and forests are because they are probably more familiar. The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs: bipartite, or 2-partite are the graphs that can be partitioned into 2 (color)classes such that no edge is internally in a class. More generally, the k-colorable graphs are exactly the k-partite graphs.
    - aleph_minus_one 2mo ago
      > The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs Be a little bit careful here: another common textbook definitions of bipartite graphs are: - a graph is bipartite iff it has no odd circle. - (for people who are into algebraic/spectral graph theory :-) ) a graph is bipartite iff its spectrum is symmetric. I personally like the latter two definitions because the "normal" definition of a bipartite graph suggests that 1-colorable, 2-colorable, 3-colorable, 4-colorable, ... graphs are conceptually very "similar" (k-colorable with different values for k). But we now that it is very easy (i.e. there exists a polynomial-time algorithm) to decide if a graph is 1- or 2-colorable, but from k=3 on, it is NP-complete to decide whether a given graph is k-colorable. Using one of these alternative definitions (and then showing "a graph is bipartite iff it is 2-colorable" as a lemma/theorem) makes it very clear that from a complexity point being 1- or 2-colorable is (assuming P != NP) something very different from being k-colorable for k >= 3.
drivebyhooting 2mo ago
Not much faster. Any k-coloring algorithm of complexity F(n) can be used to create a chromatic number algorithm of complexity lg(N)F(N) simply by bisecting on N.
- emil-lp 2mo ago
  A small tip: if you want to do this trick, with an exponential F, you probably want a linear search rather than a binary search. If your k << N then F(N/2) is going to eat up all of the running time of ΣF(i).
  - yablak 2mo ago
    Is it faster to start by doubling?
    - emil-lp 2mo ago
      It depends on F, but usually, if F is like 2^n, then a single F(i) for a too large i, is slower than computing F(j) for all j < i. This is illustrated by the fact that there are more leaves in a complete binary tree than all the other nodes summed.
in_between 2mo ago
Also see my concurrent result: https://arxiv.org/abs/2607.27159 https://arxiv.org/abs/2607.27159. Quantitatively, mine is slightly better :) my \eps_k is something like 1/2^2^2^k, Zamir gets a tower of height O(k).
- kleiba2 2mo ago
  Nice! OT: Do you happen to know anyone in the Melbourne area who works on this kind of stuff by any chance?

74 points by matt_d 3mo ago

At the end of brev paper there is a section on the LLM usage. Now, this paper will undergo peer review. And thus, when published, we will trust the result as well as any other published result in mathematics. However, while humans are not infallible, LLMs have a tendency to spit out confident stuff which looks correct. Thus I worry when it is used this way to produce proofs. Peer review is not perfect, and may not be tuned to catch LLM’s style of errors. There is a solution to this, which is to formalise the result and get it machine verified. And with LLMs, I daresay this is going to be best practice moving forward.

appplication 2mo ago
> Peer review is not perfect, and may not be tuned to catch LLM’s style of errors This summarizes I think a lot of the challenges with validating LLM output. We hear “humans make mistakes too”, but I would agree with you that our human detection of human-made mistakes and LLM-made mistakes is unlikely to have the same coverage.
- airstrike 2mo ago
  The real problem is that human mistakes generally occur more frequently given the difficulty of the task, whereas LLM mistakes are somewhat random, like the carwash problem, because LLMs cannot truly reason. I'd rather have a human on my team for whom I can reasonably surmise what tasks they're good at than have a robot who randomly gets shit wrong.
  - yndoendo 2mo ago
    I worded a questions similar to this with a person in the finance industry. He was very receptive of AI since it is one of the easiest ways to grow stock portfolio. Say you have two assistant employees. One that reads the reports and one that uses AI to summarize the content. You are sitting in a high value meeting. You only can have one assistant with you in the meeting. Which one would you pick, the persons that read the reports or the person who only used AI?
    - aleph_minus_one 2mo ago
      > Say you have two assistant employees. One that reads the reports and one that uses AI to summarize the content. You are sitting in a high value meeting. You only can have one assistant with you in the meeting. Which one would you pick, the persons that read the reports or the person who only used AI? I would take the person who only used AI. Why? Your fictional problem has the silent assumption that if you are in a high value meeting, you shall act more conservatively (i.e. reduce risk for reliability, even if you loose chances/opportunities). But this is rather a statement that the respective person acts on a risk-averse profile. I rather have a risk-affine profile. Because it is likely that everybody else in the meeting has a risk-averse profile, it is very likely that if I act on the "non-conservative" choice and I am right, I will have a huge advantage. On the other hand, if I act on the conservative choice, I won't have any advantage over the other participants. Since I am risk-affine person, I am willing to risk it. :-)
      - yndoendo 2mo ago
        There was no time frame from reading the report and AI summary to having to apply the report is stated. It could be one hour to 30 days in between or more. There was no statement if the meeting was scheduled or impromptu. Client(s) might have saw you in public or at an event. Or at a trade show and there the report only applies to the single client versus to many clients. There was no statement of report ownership. All parties might have access to it. There is a chance that AI lied / hallucinated the summary. Only to know would be taking time to read the report and validate it. AI only consumption has shown to reduce retention of information compared to reading the core content. Ever have someone tell you why they want AI? I have, it was because they do not want to read the reports.
  - gus_massa 2mo ago
    > whereas LLM mistakes are somewhat random, like the carwash problem At least in math problems, AI mistakes generally occur more frequently given the difficulty of the task. The carwash problem is very undespecified. The question should be something like "I am American. I live in a single family home in a suburb. Each member of my family has their own car. All the cars are parked during the night at home. My boss don't authorize me to go during working hour outside the office. I want to wash my car. The car wash is 50 meters away. Should I walk or drive?" Disclaimer: I am Argentinean. I live in an old apartment building without a parking lot. I don't have a car, but if I had one I'd probably move to a building with parking inside or nearby. The closest professional car washing facility is like 1000 meters away, but the closest parking lot is like 50 meters away and they guys would wash the car for a few bucks. I want to wash my car. The car wash is 50 meters away. Should I walk or drive?
    - airstrike 2mo ago
      You're picking on the specifics of the carwash problem rather than acknowledging countless other similar problems exist. The original one was strawberry, but that got RL'd away
      - gus_massa 2mo ago
        The strawberry problem is a translation/encoding problem, not a context problem. To be more efficient and cheap, the implementations use tokens, that is very-slightly-similar to translate it to Japanese: イチゴには「r」がいくつありますか？ (I don't speak Japanese, I used autotranslation, so it may be wrong.) There are no "r" in the token of strawberry.
        airstrike 2mo ago
        And yet, if models could indeed reason, that would not be an issue. You're arguing my point.

emil-lp 2mo ago

For those not familiar: K-Coloring is the property that a graph can be colored with k colors such that no two neighboring nodes get the same color. The K-Coloring problem is a decision problem, ie a yes/no question. The chromatic number of a graph is the lowest k for which it has a k-coloring. Clearly, if you have an algorithm for one, you have an algorithm for the other. The question was: is it faster to compute k-coloring than to compute its lowest (actual) k, ie its chromatic number. Forests, trees, and bipartite graphs are 2-colorable. Planar graphs are 4-colorable. It is NP-complete to check if the chromatic number of a planar graph is 3. There's a very interesting open problem, Hadwiger's conjecture that essentially says that the chromatic number is the clique (minor) number (whatever that means).

aleph_minus_one 2mo ago
> Forests, trees, and bipartite graphs are 2-colorable. More precise: a graph is bipartite if and only if it is 2-colorable (this can actually be used as a definition). Since forests are bipartite, and trees are forests, the other two statements follow.
- emil-lp 2mo ago
  Precisely! The reason I mentioned trees and forests are because they are probably more familiar. The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs: bipartite, or 2-partite are the graphs that can be partitioned into 2 (color)classes such that no edge is internally in a class. More generally, the k-colorable graphs are exactly the k-partite graphs.
  - aleph_minus_one 2mo ago
    > The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs Be a little bit careful here: another common textbook definitions of bipartite graphs are: - a graph is bipartite iff it has no odd circle. - (for people who are into algebraic/spectral graph theory :-) ) a graph is bipartite iff its spectrum is symmetric. I personally like the latter two definitions because the "normal" definition of a bipartite graph suggests that 1-colorable, 2-colorable, 3-colorable, 4-colorable, ... graphs are conceptually very "similar" (k-colorable with different values for k). But we now that it is very easy (i.e. there exists a polynomial-time algorithm) to decide if a graph is 1- or 2-colorable, but from k=3 on, it is NP-complete to decide whether a given graph is k-colorable. Using one of these alternative definitions (and then showing "a graph is bipartite iff it is 2-colorable" as a lemma/theorem) makes it very clear that from a complexity point being 1- or 2-colorable is (assuming P != NP) something very different from being k-colorable for k >= 3.

drivebyhooting 2mo ago

Not much faster. Any k-coloring algorithm of complexity F(n) can be used to create a chromatic number algorithm of complexity lg(N)F(N) simply by bisecting on N.

emil-lp 2mo ago
A small tip: if you want to do this trick, with an exponential F, you probably want a linear search rather than a binary search. If your k << N then F(N/2) is going to eat up all of the running time of ΣF(i).
- yablak 2mo ago
  Is it faster to start by doubling?
  - emil-lp 2mo ago
    It depends on F, but usually, if F is like 2^n, then a single F(i) for a too large i, is slower than computing F(j) for all j < i. This is illustrated by the fact that there are more leaves in a complete binary tree than all the other nodes summed.

in_between 2mo ago

Also see my concurrent result: https://arxiv.org/abs/2607.27159 https://arxiv.org/abs/2607.27159. Quantitatively, mine is slightly better :) my \eps_k is something like 1/2^2^2^k, Zamir gets a tower of height O(k).

kleiba2 2mo ago
Nice! OT: Do you happen to know anyone in the Melbourne area who works on this kind of stuff by any chance?