expected size of a special set of random points in the unit square Today I came up with this fun problem, but I'm having a hard time to solve it completely myself. The question is the following:
Let's generate n random points independently in the unit square uniformly, label the points $p_1, p_2, ..., p_n$, let $S$ be the largest set such that for any $i, j\in S$, $p_i, p_j$ form a line with a negative slope.
Now, what is the expected size of the set $S$? i.e. $E(|S|)$? a lower bound on it? an upper bound?
What I have so far is based upon the geometric intuition of the problem, so assume we already have i points in the unit square that are all in the set $S$, so that they all form pairwise negative sloped lines. Let's consider the $i+1$th point, and how its possible position might effect the size of the set $S$.
What I would do at each point $p_i$, draw a cross centered at the point $p_i$. So given the first $i$ points, the unit square would be divided into $(i+1)^2$ little rectangles. Start from the top left corner of the unit square, there would be a little rectangle whose top left corner is the top left corner of the unit square, and the diagonal starting from the top left corner would lead us to the top left corner of the next little rectangle. So continue down this path of diagonals until we get to $(1, 0)$, the lower right corner. Let's call the rectangles with those diagonals the diagonal rectangles.
It shouldn't be hard to see that if the $i+1$th point is in any of the diagonal rectangles, then the size of the set $S$ would increase by $1$. Similarly, if this point lands in any of the two lanes of off-diagonal rectangles, then $|S|$ doesn't change, and $|S|$ would decrease by $1$ if the point lands one lane further than the off-diagonals, $-2$ if two lanes further..., etc.
I think the reasoning above is correct, but I'm having a hard time translating those words into equations to get me an analysis on the size of $S$. Thank you for your help!
Also just to simplify things a bit, let's assume no two points would form a horizontal or vertical line.
 A: Without loss of generality, let's sort the points by $x$-coordinate, so that $p_1$ is the left-most point and $p_{n}$ is the rightmost point. 
Now, consider the following observation. If $p_{i}$ and $p_{j}$ both belong to $S$, with $i < j$, then $y_{j}$ (the $y$-coordinate of $p_{j}$) must be less than $y_{i}$; if not; then $p_{i}$ and $p_{j}$ for a line with positive slope.
Since all that matters is the relative ordering of the $y_{i}$s, we can assign each $p_{i}$ a label $\pi_{i}$ if it has the $i$th largest $y$-coordinate. These labels $\pi_{i}$ define a permutation $\pi$ of the numbers $1$ through $n$. Note that, since the $y$-coordinates are independent of the $x$-coordinates, each of the $n!$ different permutations $\pi$ are equally likely.
But now, the maximum size of $S$ is just the length of the longest decreasing subsequence in $\pi$, so $\mathbb{E}[S]$ is just the length of the longest decreasing subsequence of a uniform random permutation.
Unfortunately, there isn't an exact closed form for this quantity, but it has been very well studied. In particular, it's known that, asymptotically, $\mathbb{E}[S] \approx 2\sqrt{n}$; see these papers for many references. 
