12
$\begingroup$

This is a question inspired by and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly much easier!

Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each edge of $K_n$, and then sums the incident edge weights to each vertex and assigns those as vertex weights. For example, here is $K_5$ with edge weights from $\{1,2,3,4,5\}$:
      EVColoringPentagon
(The top vertex has weight $13=3+1+4+5$.) In this case, the vertex weights do not form a proper coloring, because there are two vertices assigned weight $14$.

What is the probability that $K_n$ will be properly colored when the edge weights are chosen uniformly from among $\{1,2,3,\ldots,k\}$?

Empirically the function is well-behaved. Here is an accounting over $1000$ trials on $K_5$ for each $k$ from $3$ to $20$:
      EdgeVertexColoring


As requested, a plot of Lucia's $e^{-\frac{\sqrt{\frac{3}{\pi }} n^{3/2}}{2 k}}$ for $n=5$ (with $k$ on the horizontal axis):
   Lucia30

$\endgroup$
  • 2
    $\begingroup$ You can estimate the probability that two particular vertices have the same sum and then use the union bound. $\endgroup$ – Douglas Zare Nov 10 '13 at 5:50
  • 1
    $\begingroup$ First guess: Adding $n-1$ random elements (with replacement) from $1$ to $k$ gives some distribution on $(n-1)$ to $k(n-1)$. Then one is essentially solving the birthday problem for $n$ objects from that distribution. $\endgroup$ – Lucia Nov 10 '13 at 15:17
  • $\begingroup$ @JosephO'Rourke: Would it be possible to plot $\exp(-\sqrt{3}n^{3/2}/(2\sqrt{\pi}k))$ on your graph? Just eyeballing it, the fit seems like it would be reasonable. $\endgroup$ – Lucia Nov 12 '13 at 16:44
  • $\begingroup$ @Lucia: I think you mean $1-\mathrm{exp}(...)$. $\endgroup$ – Joseph O'Rourke Nov 12 '13 at 18:18
  • 1
    $\begingroup$ @Lucia: In my excitement I switched $n$ and $k$, as you suspected---Sorry! Very close match. Brilliant! Congrats! :-) $\endgroup$ – Joseph O'Rourke Nov 12 '13 at 19:29
7
$\begingroup$

Here's a heuristic which suggests that the right scale for $k$ is on the order of $n^{3/2}$, and predicts the actual probability for large $n$. More precisely, we conjecture the following: Let $n$ be large, and suppose $k$ is close to $t n^{3/2}$ and we have in mind that $t$ is of roughly constant size. Then the probability that one gets a proper coloring is (as $n$ goes to infinity) asymptotically $\exp(-\sqrt{3}/(2\sqrt{\pi}t))$. As $t$ goes to zero this is exponentially small, and as $t$ goes to infinity it tends to $1$ at a linear rate.

Here's the reasoning: If $X_1$, $\ldots$, $X_n$ are chosen uniformly (with replacement) from $1$ to $k$, then the sum $X_1+\ldots+X_n$ has mean $n(k+1)/2$ and variance $n(k^2-1)/12$, and for large $n$ it is approximately normal with this mean and variance. Therefore the sums for each of the $n$ vertices has mean $n(k+1)/2$ and wiggles around that on the scale of about $\sqrt{n}k$. Let us imagine that different vertices have independent sums -- this is not quite true because they share an edge, but I would expect that effect to be small (this is a heuristic, not a proof after all!). Then we have a situation like the birthday problem: Pick $n$ numbers from an interval of length about $\sqrt{n}k$, what is the chance of a coincidence. From the birthday problem we know that if $n^2$ is of size $\sqrt{n}k$ then there is a good chance of a coincidence. (Note that for the proper coloring we want there not to be a coincidence of sums.) This suggests that $k$ of size $n^{3/2}$ is the correct scaling. The actual formula was obtained by computing the analog of the birthday problem in this Gaussian setting (which is a nice exercise).

The only thing preventing this from being a proof is the lack of independence for the sums at two vertices -- I think this can be fixed, but will need a better probabilist than me!

$\endgroup$

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.