I'm struggling with the following problem:


Consider two sets A and B containing m and n nodes. These sets are connected by l edges. Each edge connects one node from A to one node from B.

Boundary of set A is the subset of its nodes that are connected (by edges) to set B. I'm looking for the expected size of this boundary.

I would like to use this expected size to answer the question "What is the probability, that a node from A is exactly one edge away from closest node in set B".


Lets consider sets A and B to have two nodes each.

If there is one edge: Expected boundary of A is 1.

If there are two edges, there are possibilities:

       1)        2)        3)         4)        5)     6)
       A   B     A   B     A   B      A   B     A   B   A    B
       * - *     * - *     * - *      * \ *     * / *   * \/ *
       * - *     * / *     * \ *      * - *     * - *   * /\ *
b(A)=   2          2         1           2        1        2

Expected b(a) = 10/6

and so on..

My tries

What I've considered is representing the problem with a matrix of size n x m with l where each sell is a possible edge. Then l cells would be filled. There would be: $ |\Omega|={{nm}\choose{l}} $ possibilities.

Then I tried to count number of ways i rows can be populated (with l) cells to get the probability of boundary size i. I assume that would be number of ways different l of ${im}\choose{l}$ objects can be placed in different i bins where none of them is empty.

I've looked at the stars and bars but here it considers identical objects and thats not the case.

It also looks similar to sum of multinomial coefficients but with the limitation that counts in each bin ($k_i$ in wikipedia article) must be positive.

But I may be going in the wrong direction entirely. Thank you for replies.

  • $\begingroup$ Just to understand it right, what is the size of the "boundary" if the graph has two or more connected components? $\endgroup$ – Jack D'Aurizio Aug 19 '14 at 23:05
  • $\begingroup$ @JackD'Aurizio I've added an example, hope it clarifies... $\endgroup$ – Szymon Małczak Aug 19 '14 at 23:39
  • 1
    $\begingroup$ Not clear for me. "Each each is unique" (?) "one node from A can be connected to any number of nodes from B" (and viceversa, no?) "Connected nodes form a boundary of the set" (are you speaking of the set A?). Is the total number of edges fixed? "Expected number"... with respect of what probability law? $\endgroup$ – leonbloy Aug 19 '14 at 23:51
  • $\begingroup$ Not clear for me too. Are you simply asking for the average value of $|f(L)|$ where $f:L\to A$ and $|L|=l,|A|=m$? $\endgroup$ – Jack D'Aurizio Aug 19 '14 at 23:57
  • $\begingroup$ @leonbloy I've updated the definition of edge. Yes, it's boundary of set A. Number of edges is a variable. $\endgroup$ – Szymon Małczak Aug 20 '14 at 7:02

If I understand the problem right: given that the number of edges $\ell$ is fixed, there are a total of $m \times n$ pairings possible, so the total number of alternatives is ${mn \choose \ell}$. How many of these involve exactly $k$ elements (out of $m$) from $A$? This is

$$g_k={m \choose k} \left[ {k\,n \choose \ell}-{(k-1)\,n \choose \ell}+{(k-2)\,n \choose \ell}-\cdots\right]={m \choose k} \left[ \sum_{j=0} {(-1)}^j{(k-j) \,n \choose l} \right]$$

And the expected number is $$\frac{1}{{m\,n \choose \ell}}\sum_k g_k$$

This is, of course, not a complete solution. But I'm not sure if I'm on the right track.


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.