2
$\begingroup$

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$?

Improve this question
$\endgroup$
6
  • $\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
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 at 21:15

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\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
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 at 21:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .