[25] Consider a random directed graph whose n2 nodes are on the intersections of a two-dimensional n by n grid. All vertical edges

(the grid edges) are present and directed upward. For every pair of horizontally neighboring nodes, we flip a three-sided coin; with probability p < 1 2 we add an edge from left to right, with probability p we add an edge from right to left, and with probability 1 − 2p we add no edge. Use incompressibility to prove that the expected maximum path length over all such random graphs is bounded by O(n).
Comments. Source: T. Jiang and Z.Q. Luo, personal communication, 1992. This problem was studied in connection with communication networks.