I have generated a single random 17th degree 100 vertex graph, with self-loops and multiple edges rerandomized out of existence, so the graph is highly 17 regular, and after long computation with a satisfiability solver, generated a 6 coloring. The graph and its coloring are available by email.

Presently, my three new (tight) claims are:

Almost all 9 regular graphs are 4 colorable. (many random examples)

Almost all 13 regular graphs are 5 colorable. (some random examples)

Almost all 17 regular graphs are 6 colorable. (one random example)

(Almost all 5 regular graphs are 3 colorable is well known, the others are new.)

The tightness of theorem 1.1 means these graphs are very difficult to k-color. I would like to know when the increment by 4 in the degree will fail with the increment in number of colors, for future work.

Main question: Is the single successful randomly generated 17 regular graph at some number of vertices (100) sufficient to prove the almost all 6 colorability claim?

Second question: Does the result help improve the error terms in the previously cited paper (theorem 1.1 of the paper, "On the chromatic number of random regular graphs.")? I want to predict whether 21 regular graphs are worth exploring for 7 colorings...

  • 1
    $\begingroup$ In what sense do you mean 'almost all'? $\endgroup$ – Per Alexandersson Apr 13 '17 at 10:35
  • $\begingroup$ Can you provide a link (perhaps to Arxiv) for the paper you cite ( "On the chromatic number of random regular graphs.")? $\endgroup$ – Vincent Apr 13 '17 at 11:22
  • $\begingroup$ I just randomly generated a 2-regular graph on 4 vertices and it is 2-colorable. How could that possibly prove anything? $\endgroup$ – monkeymaths Apr 13 '17 at 11:23
  • $\begingroup$ I guess it is this one: arxiv.org/pdf/1308.4287.pdf, but since you didn't name the authors I am a bit hesitant to edit it in myself - perhaps there is some other paper with the same name somewhere $\endgroup$ – Vincent Apr 13 '17 at 11:24
  • $\begingroup$ The authors are Amin Coja-Oghlan Charilaos Efthymiou Samuel Hetterich. Almost all means the probability of the property approaches 1 as the number of vertices grows larger. monkeymaths gets a banana for the effort put into that result. I have put alot of effort into these results... $\endgroup$ – daniel pehoushek Apr 13 '17 at 13:10

The answer to your main question is no. As monkeymaths has mentioned, there is no way to get a theorem about statements of the form 'almost all' from a single example. However, the computation you are describing can very strong evidence that such a theorem is true. Even if the 'might' is $(1/2)^{1,000,000,000}$ as you suggest, one example still won't prove a theorem, though at that point we should probably consider it more compelling than a peer-reviewed proof. For a "gold mining theorem" (your words) to hold in the context of $d$-regular graphs, we would need to know:

  1. The procedure to generate your instance is truly random (or even sufficiently random)
  2. The method to compute the chromatic number of the graph is accurate
  3. For every $d$ (or that value of $d$), the chromatic number concentrates on a single integer value with high probability
  4. A method to bound the probability that a random instance deviates from the likely outcome as a function of $d$ and $n$

The fundamental problem with this outline is that (3) and (4) combine to form a complete proof, so there is no need for (1) and (2). If Theorem 1.1 of On the chromatic number of random regular graphs is the state of the art, then (3) is only known for an asymptotically dense subset of $\mathbb{N}$ that does not appear to be explicit, so your choice of $d$ might not belong to it. Additionally, they do not provide any progress on (4) for values of $d$ when (3) holds. If you choose to believe (3) and (4) are true, then (1) and (2) forms very strong evidence, but not a proof.

With this said, I think that there is a great deal to learn from the types of computations outlined in (1) and (2). I can point to several instances where a single large example has convinced me that a theorem is true (as opposed to proved), but this relies on assuming that the answer will take a certain form (3) and that the size of the example is big enough (4). However, these assumptions need to be demonstrated to know for certain a theorem is true. I've had experiences where such assumptions failed and a result I believed true was actually false, as have many others.


Since random regular graphs have the strong coloring transition from probability 0 for small graphs to probability 1 for large graphs, finding any large graph with a proven coloring is equivalent to showing that almost all such regular graphs are likewise colorable.

So, having an existential proof (an actual 6 coloring) for a single degree 17 100 vertex graph is equivalent to proving that almost all such graphs are likewise colorable. Without an existential example, the transition to probabilty 1 is unknown. And, likewise, the probability that the given randomly generated graph was a lucky fluke is also small (probability asymptotically 0).

I would still appreciate a more general "gold mining theorem of regular graphs" for existential searches of other monotone properties.

  • $\begingroup$ I do not understand the negative votes. I have worked for years on graph coloring, and the 9 regular 4 coloring, 13 regular 5 coloring, and 17 regular 6 coloring, are all unknown and very hard to compute. They are good results. Are they unimportant here? I think a "gold mining theorem" would be a premium theorem, and I was hoping it had already been done. $\endgroup$ – daniel pehoushek Apr 15 '17 at 1:25
  • $\begingroup$ By hard to compute, I mean NP-hard. Solving these instances takes two cpu weeks per graph, and I have just over fifty of them. $\endgroup$ – daniel pehoushek Apr 15 '17 at 1:48
  • 1
    $\begingroup$ The point is that your 'gold mining theorem' is merely wishful thinking. For any $r$ there are arbitrarily large bipartite $r$-regular graphs. For any fixed $k \geq 2$ and arbitrarily large $N$, there is a non-zero probability that a "large" (more than $N$ vertices) randomly generated $r$-regular graph is $k$-colourable (because it is in fact even bipartite), although it is not the case that "almost all" $r$-regular graphs are $k$-colourable. $\endgroup$ – monkeymaths Apr 19 '17 at 9:22
  • 1
    $\begingroup$ So you're saying that it is wrong that there is a non-zero chance that a randomly generated 100-regular graph happens to be 2-colorable? $\endgroup$ – monkeymaths Apr 24 '17 at 8:28
  • 3
    $\begingroup$ But taking a single sample might just give a graph which is in the 'asymptotically zero'-set, so it might actually not be 'asymptotically possible'. You then arrive at a wrong conclusion. Taking a random 100-regular graph on a million vertices, it is possible that this graph happens to be 2-colorable. If your Gold Mining Theorem were correct, you would then be led to conclude that almost all 100-regular graphs were 2-colorable. But this is false. Hence your Gold Mining Theorem is false. If you do not understand this, we cannot help you here. $\endgroup$ – monkeymaths Apr 25 '17 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.