4
$\begingroup$

Suppose I embed $K_4$ (the complete graph on 4 vertices) randomly in the unit square (using the uniform distribution for the positioning of the vertices). $K_4$ is planar, but not any embedding of it is a plane graph. What is the probability that the embedding will be a plane graph?

[Edit: when I say embedding, I mean an embedding of the vertices as points and embedding of the edges as straight line segments connecting their vertices; I am not sure this was clear]

Is the result different when we take the unit circle instead, or if we embed it in $\mathbb{R}^2$ using Gaussian distribution?


Update

An equivalent question would be that: given a random triangle, what is the probability that a random selected point will lie in it. For the uniform distribution on the unit square, that had been asked already here and answered here.

I have not verified the solution presented there, but if it is correct, the probability of the random embedding of $K_4$ in the unit square is $\frac{11}{144}$. This does not solve the unit circle case or the Gaussian case, however, and I am not convinced this should be similar at all.

$\endgroup$
2

1 Answer 1

1
$\begingroup$

If I understand well your question, this is equivalent to the Sylvester's Four-Point Problem. You want to know the probability that one of the point is inside the triangle formed by the 3 other points. When the points are i.i.d. uniformly in a square then it is $\frac{11}{36}$. The probability $\frac{11}{144}=\frac14\frac{11}{36}$ you mentioned is the probability that the first point is in the triangle formed by the $3$ others, but we do not care which point is inside, so we should multiply by it $4$ to obtain the correct probability.

If the points are uniformly distributed in a disk (or more generally an ellipse) then the probability is $\frac{35}{12\pi^2}$ (see the previous link).

$\endgroup$
2
  • $\begingroup$ and I don't remember about when the points are normally distributed, but I think I heard it once. I might be able to find a reference if you are still interested. $\endgroup$ Commented May 9, 2014 at 23:37
  • $\begingroup$ It took me a while to read your answer, but it is helpful still, thanks! $\endgroup$
    – Bach
    Commented Oct 28, 2015 at 12:13

You must log in to answer this question.

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