1
$\begingroup$

Consider an unweighted and undirected graph $G=(V,E)$, where the vertices $V$ of $G$ lie on the unit n-sphere. If we choose a normal vector uniformly at random on this $n$-sphere, then the corresponding hyperplane (shifted to go through the origin) splits the vertices into two disjoint sets $A$ and $B$, and the expected number of edges cut by this hyperplane is $$ \mathbb{E}[Cut(A,B)] = \sum_{(i,j)\in E}\frac{\arccos(v_i\cdot v_j)}{\pi}\; . $$

So I understand that $\frac{1}{\pi}\arccos(v_i\cdot v_j)$ is basically the probability that a randomly chosen hyperplane which goes through the origin will separate $v_i$ and $v_j$. But I can't grasp how this sum is equal to the expectation described above.

Also, can this sum be extended to work for weighted graphs?

$\endgroup$
  • $\begingroup$ This makes no sense... $A$ and $B$ are random ; how could they appear in the right-hand side ? $\endgroup$ – D. Thomine Nov 2 '15 at 20:27
  • $\begingroup$ @D.Thomine You're right, I just edited it so now it should be correct. $\endgroup$ – Thoth Nov 2 '15 at 20:39
1
$\begingroup$

This merely comes from the linearity of the expectation, in a way which is quite similar with Buffon's noodle.

Let $(i,j)$ be an edge. Let $X_{ij}$ be the random variable whose value is $1$ if the random hyperplane crosses $(i,j)$, and $0$ otherwise.

Then :

  • $\mathbb{E} (X_{ij})$ is the probability that the random hyperplane crosses $(i,j)$, so that:

$$\mathbb{E} (X_{ij}) = \frac{\arccos(v_i \cdot v_j)}{\pi}.$$

  • The total number of edges that the random hyperplane crosses is:

$$Cut(A,B) = \sum_{(i,j) \in E} X_{ij}.$$

Hence,

$$\mathbb{E} (Cut(A,B)) = \mathbb{E} \left(\sum_{(i,j) \in E} X_{ij} \right) = \sum_{(i,j) \in E} \mathbb{E} \left( X_{ij} \right) = \sum_{(i,j) \in E} \frac{\arccos(v_i \cdot v_j)}{\pi}.$$

$\endgroup$
  • $\begingroup$ wow so simple, I guess I needed to correctly formulate my $X_{ij}$ like you did. $\endgroup$ – Thoth Nov 2 '15 at 21:56
1
$\begingroup$

This is an application of Crofton's formula (on the sphere), also called the Cauchy-Crofton formula.

More generally, if C is a rectifiable curve on $S^n$, the unit sphere in n dimensions, then the length of C is equal to $\pi$ times the average number of times a great sphere intersects C. A great sphere is the intersection of the unit sphere with a hyper-plane passing through the sphere's origin, and the average is taken over the space of all great spheres (with the natural measure on that space). The same applies when C is a (finite) set of rectifiable curves.

For example, a great circle intersects almost every great sphere in two points (which happen to be diametrically opposite), so this formula tells us that the length of a great circle is $2\pi$.

In your case, you can apply this formula to the set of edges of your graph. Each edge is a geodesic arc (an arc of a great circle). The formula tells us that the average number of times a great sphere intersects the set of edges (which is the expected number of edges cut by the corresponding hyper-plane) equals $\pi$ times the sum of the lengths of the edges. The $i^{th}$ term in your sum is the length of the $i^{th}$ edge divided by $\pi$, so you see that your formula follows immediately from Crofton's formula on the unit n-sphere.

An intuitive pseudo-proof of Crofton's formula is as follows. Both sides of the formula are invariant under rotations of the sphere, and both sides are "additive" in the sense that the value for a set S composed of disjoint pieces $S_1$, $S_2$, ..., $S_k$ is the sum of the values for the separate pieces (e.g., consider a curve divided into a finite number of segments). Assuming continuity of both sides when a rectifiable curve is approximated by polygons (recall that this is a pseudo-proof), this reduces the claim to the case when the curve C is a geodesic arc, and in that case additivity an continuity imply that both sides are linear functions of the arc length, hence they are proportional. The multiplicative factor can be determined by evaluating both sides of the formula for a curve with known length, such as a great circle.

Crofton's formula, properly formulated, also holds in the plane (and more generally in n-dimensional Euclidean space) and in hyperbolic space. The pseudo-proof above applies to those cases as well.

Crofton's formula plays a central role in John Milnor's proof that a knotted space curve must have total curvature at least $4\pi$.

$\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.