In this paper "Probability that n random points are in convex position" by Pavel Valtr I followed through with everything until in page 4 when he introduces the idea of a property $P_{i,j}$
I dont understand what the property is implying or what $i$ and $j$ are supposed to be.
And also why is,
the number of the 4-tuples satisying $P_{i,j} = {{n-2}\choose i}{m\choose n}{{n-2}\choose j}{m\choose n}$
So if someone could explain the following points I would be very grateful
- What is the significance of $P_{i,j}$ and how does it relate to convexity of the set
- What are $i$ and $j$ and why do they need to be $ \le n-2$
- How does the definition of $P_{i,j}$ imply the above equation
Thank you for your time
To keep this question self-contained, a brief description of property $P_{i,j}$: a 4-tuple $(D^-,E^-,D^+,E^+)$ of subsets of $\{1,2,\dots, m\}$ has this property if $|D^+|=i+2$ and $|E^+|=j+2$; and $|D^-|+|D^+|=|E^-|+|E^+|=n+2$; and also $\min D^- = \min D^+$ plus the three analogous equalities with max's and E's.
A small mistake in the OP: The expression ${{n-2}\choose i}{m\choose n}{{n-2}\choose j}{m\choose n}$ is stated to count the number of 4-tuples satisfying $P_{i,j}$ and with $|D^-\cap D^+|=|E^-\cap E^+|=2$. Note that these two elements in both D's must necessarily be the min and the max, and same for the E's.
Moreover, apply inclusion-exclusion (or just Venn diagram it) to see that there are $n$ distinct elements in $D^-\cup D^+$. Therefore the $\binom{m}{n}$ is simply choosing which $n$ elements show up in that union. Since the minimum and maximum of these $n$ elements must be in both $D^-$ and $D^+$, we need to choose $(i+2)-2$ more elements from the $n-2$ non-min-or-max elements to fill up $D^+$, yielding the $\binom{n-2}{i}$. Once this has been done, $D^-$ is uniquely determined, since it contains exactly the other non-min-or-max elements, as well as the min and max.
Exactly the same argument holds for the E's, with $j$ instead of $i$, and these two choices are independent, so all the binomials get multiplied together.