Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

k-Coloring is Faster than Computing the Chromatic Number

arxiv.org

Post reply on HN
Print view View original

11–15 of 15 posts

Re: k-Coloring is Faster than Computing the Chromatic Number

#11

Post by aleph_minus_one »

emil-lp wrote: post #9
aleph_minus_one wrote: post #8

Earlier quoted context omitted.

> 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.

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.

> 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.

Re: k-Coloring is Faster than Computing the Chromatic Number

#12

Post by gus_massa »

airstrike wrote: post #5
appplication wrote: post #3

Earlier quoted context omitted.

> 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.

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.

> 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?

Re: k-Coloring is Faster than Computing the Chromatic Number

#13

Post by LegionMammal978 »

aleph_minus_one wrote: post #11
emil-lp wrote: post #9

Earlier quoted context omitted.

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.

> 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…

One curiosity that in the case of infinite graphs, "no odd cycles" doesn't imply "2-colorable" without the axiom of choice for families of 2-element sets [0]. It's somewhat similar to how in the definition of a well-founded relation, "no infinite descending chains" doesn't imply "every nonempty subset has a minimal element" without dependent choice.

(One of my recent projects has been trying to prove the existence of a 2-colorable subgraph for a certain class of infinite graphs in ZF, which has led me surprisingly deep into choice principles and models refuting them.)

[0] https://mathoverflow.net/a/453944

Re: k-Coloring is Faster than Computing the Chromatic Number

#15

Post by kleiba2 »

in_between wrote: post #14

Also see my concurrent result: 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).

Nice!

OT: Do you happen to know anyone in the Melbourne area who works on this kind of stuff by any chance?

Post reply on HN