There are N points on the plane and the probability that the probability that two points are connected is p. What is the expected number of Quadrilaterals you can find? Assume that there is no three points on the same line. A quadrilateral is defined as a set of four edges that bound a polygonal region.

Is there any close form solution to this question? For $N=4$, it is just $p^4$, but $N=5$ we have to consider all the possibilities from 1~5 Quadrilaterals.

  • $\begingroup$ It sounds like we're supposed to assume the point connections occur independently. But what exactly is a "quadrilateral"? The example makes it look like a quadrilateral must be a set of four edges that bound a polygonal region; but it could mean any sequence of four points connected by edges (modulo cyclic rotation and reversal) as well as other variations on that theme. $\endgroup$ – whuber Mar 13 '19 at 19:08
  • $\begingroup$ @whuber Thanks for the comment. I have clarified the problem. $\endgroup$ – James Mar 13 '19 at 19:15
  • $\begingroup$ That helps, thank you. But in light of what you have written, it seems to me the answer must depend on the specific configuration of the points. Even with $N=4$ the answer can be $3p^4$ or $p^4$ depending on whether the convex hull of the points is a triangle or a quadrilateral, respectively. What, then, are you assuming about the point configuration that would enable a unique answer to be provided? $\endgroup$ – whuber Mar 13 '19 at 19:20
  • $\begingroup$ @whuber This is a very good point! I think we can start assuming the convex hull is always a quadrilateral. Btw, this is actually an open question so I guess we can start from any reasonable assumption at the moment. $\endgroup$ – James Mar 13 '19 at 19:50
  • $\begingroup$ Assuming all convex hulls of all subsets of four points are quadrilaterals is a severe restriction: it implies the configuration is essentially that of a sequence of $N$ points placed on a circle. $\endgroup$ – whuber Mar 13 '19 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.