Leandro, you are right. I will think about this some more...

You mention Erdos-Renyi random graphs $G(n,p)$ below. Note that making $p=c/n$ with $c$ fixed might be unnecessarily restrictive. If $p$ is just slightly larger, i.e. $p \ge (1+\epsilon) \log n / n$ with $\epsilon > 0$ fixed, then the random graph is connected with probability one. As far as I can tell the question about sandpile groups makes sense and is interesting for this (or any larger) function $p=p(n)$. An interesting alternative would be to consider sandpile groups of $d$-regular graphs. Already when $d=3$ these are connected with probability one.

See also Terence Tao's answer to this question: mathoverflow.net/questions/38161/…

I believe that what I stated above is the Charney-Davis conjecture, at least one version or one case of it. What I am asking for are more general versions of it.

More generally, all graphs (whether planar or not) of maximal degree 4 are 4-colorable, with the complete graph $K_5$ being the only exception. This is covered by Brooks' Theorem. en.wikipedia.org/wiki/Brooks%27_theorem My only concern with this argument is if we also want to color the external face, and then every vertex in the dual graph has degree >= 5.

I finally understand what you are asking --- to clarify you might indicate that the $k$-tuples in your graph are ordered k-tuples.