# Coloring $K_n$ via edge-weight sums

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\}$: (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$: 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): • You can estimate the probability that two particular vertices have the same sum and then use the union bound. – Douglas Zare Nov 10 '13 at 5:50
• 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. – Lucia Nov 10 '13 at 15:17
• @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. – Lucia Nov 12 '13 at 16:44
• @Lucia: I think you mean $1-\mathrm{exp}(...)$. – Joseph O'Rourke Nov 12 '13 at 18:18
• @Lucia: In my excitement I switched $n$ and $k$, as you suspected---Sorry! Very close match. Brilliant! Congrats! :-) – Joseph O'Rourke Nov 12 '13 at 19:29

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