I am stuck at this question. I think it should be somehow related to the order statistics and have a rough idea. However, I do not have something convincing enough. Thanks for any help in advanced!
Consider a tri-partite graph on d + 2 vertices, where there is one vertex on the left (call it A), one vertex on the right (call it B) and d vertices in the middle. The graph has 2d edges, d connecting A to the middle and d connecting B to the middle.
Assume now each vertex is uniformly assigned a value from [0,1], independently. Let $E_1$ be the event that A is the local maximum and $E_2$ be the event that B is the local maximum. Compute or give an upper bound on $Pr[E_1 \cap E_2]$.
If "local maximum" means value $A$ is greater than the $n$ values it is connected to and value $B$ is also greater than the same $n$ values it is connected to then the answer is $$\Pr[E_1 \cap E_2]=\frac{1}{n+2 \choose 2} = \frac{2}{(n+1)(n+2)}$$ by considering whether $A$ and $B$ take the top two values of all of the $n+2$ values