Imagine I have an $N$ by $M$ rectangular lattice where I randomly assign one of $k$ colors to every vertex in the lattice. I then write down a list of the ${N*M}\choose{2}$ possible unordered pairs of vertices, noting the color of each vertex in a pair and the Euclidean distance between them. Finally, I count the number of pairs of vertices with the both the same vertex color combination and Euclidean distance as a previously recorded pair, $P$. For example, if I've previously recorded a "red" and a "blue" vertex with Euclidean distance $d_i$ between them, which we'll write as a tuple: {$c_1, c_2, d_i$}, another example of a "red" and "blue" vertex pairing with the same Euclidean distance, {$c_1,c_2,d_i$} or {$c_2,c_1,d_i$} (order of the colors does not matter), would increase $P$ by one.

With a hat tip to Gerhard Paseman, we can write that $P = $${N*M}\choose{2}$$-T$, where $T$ is the total number of distinct tuples: {$c_i,c_j,d_k$}, where the order of the colors do not matter and vertices of the same color are allowed.

As a function of $N$, $M$, and $k$, what is the expected value of $P$?

  • $\begingroup$ Honestly, I would be very surprised if someone posts an exact answer... though that's obviously very welcome. I'm interested in how well one can do on bounding the value of P. $\endgroup$ – Polyrhythm Jul 17 '12 at 3:13
  • 1
    $\begingroup$ You might provide an explicit example for further clarity. Suppose I count the number of types T of (Distance, color1, color2) tuples that occur for a particular coloring. Then P + T = mn choose 2, by my interpretation of P. If so, that gives you a good start on bounds right there, especially for small colors. Gerhard "Did I Get That Right?" Paseman, 2012.07.17 $\endgroup$ – Gerhard Paseman Jul 17 '12 at 17:34
  • $\begingroup$ @Gerhard Paseman, Given that the elements within the tuples are unordered, that you wouldn't count {1, color1, color2} and {1, color2, color1} as distinct, yes, exactly: $P+T =$ ${N*M}\choose{2}$ according to your definition of T. $\endgroup$ – Polyrhythm Jul 17 '12 at 18:58
  • 1
    $\begingroup$ In fact, it is an interesting problem just to consider the multiplicity function m(d) suggested by Douglas Zare. When N/M is large, m(d) is often a simple function of m and n, and decreases something like 1/d^2, so you will find the answer not very influenced by the number of colors used. I recommend focusing on m(d) for M < N < 3M, say. Gerhard "Ask Me About Sysem Design" Paseman, 2012.07.17 $\endgroup$ – Gerhard Paseman Jul 17 '12 at 19:05
  • $\begingroup$ @Gerhard Paseman, I think you've made a very good suggestion, however one of my interests here is to understand the number of colors, $k$, one needs to obtain a specific value of $P$. $\endgroup$ – Polyrhythm Jul 17 '12 at 21:15

Here is a little data (not an answer) for small arrays for anyone who wants to compare against a theoretical calculation. I looked at square $n \times n$ arrays, $k=2$ colors only. Here are the counts for $P$, after $100$ random trials: $$ (2, 2.4), (3, 24.2), (4, 95.5), (5, 260.3), (6, 575.0), (7, 1100.1), (8, 1919.0) $$ In other words, just to interpret the last piece of data: In random $8 \times 8$ arrays, of the $\binom{64}{2}=2016$ pairs, there were on average $T=97.0$ distinct distance/color pairs (using Gerhard's definition for types $T$), leaving $P=1919.0$ repeated pairs; note $T+P=2016$. (In one trial, the distance $\sqrt{65}$ and colors $(2,2)$ occurred only once, whereas the distance $\sqrt{41}$ and colors $(1,2)$ occurred $25$ times.) Here is a graph of the same data:
          Coloring Lattice Plot

Added. Now that the OP has indicated an interest in variation with the number of colors $k$, here is the same type of data, but for $k=2,3,4,5,6$:
          2,3,4,5,6 colors

| cite | improve this answer | |
  • $\begingroup$ @Joseph O'Rourke, very nice! Just to clarify, I originally meant $P$ as the sum of all repeats over all pair color and distance combinations. It doesn't really matter, but are you assuming $P$ is an average number of repeats for a particular pair color combination and associated distance? $\endgroup$ – Polyrhythm Jul 17 '12 at 17:00
  • $\begingroup$ I think I followed your intent. For each distance/color combination that occurred, I counted up the number of repeats of that combination. Then I averaged over all such distance/color combinations. So in one $8 \times 8$ run, there were 98 such distinct combinations, with varying counts. So for the mean I divided by 98 (and not by the possible number of distance/color combinations, many of which do not occur in any given run). $\endgroup$ – Joseph O'Rourke Jul 17 '12 at 17:36
  • $\begingroup$ @Joseph O'Rourke, I think we're more or less on the same page, except that I originally meant $P$ as the sum of the total number of repeated pairs, not the average (which is totally fine). Just to explain my original definition, on your 8 x 8 run, if an arbitrary pair has already occurred and you see another instance of it, you'd increment $P$ by one. In other words, if I see two pairs of, arbitrarily, "red" and "blue" vertices, both with distance one, and this is the only repeat I encounter on the grid, $P = 1$. $\endgroup$ – Polyrhythm Jul 17 '12 at 18:51
  • $\begingroup$ @Joseph O'Rourke, I think Gerhard Paseman provides a better description for my original meaning of $P$ in his comment below the original question. $\endgroup$ – Polyrhythm Jul 17 '12 at 18:59
  • $\begingroup$ Indeed I had not understood your definition of $P$. I now follow Gerhard's $T+P$ formulation. $\endgroup$ – Joseph O'Rourke Jul 17 '12 at 21:17

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.