I came across a problem in complexity theory which I believe reduces to the following graph theory problem. I am not familiar with discrete math and so I do not know how to approach this problem. Does anyone have a solution, or can anyone recommend a source that might help me?

The problem:

Let n and r be parameters. We are interested in r being constant, or at least very small compared to n (say r=loglog(n)). We have a directed n-partite graph G, with vertex sets V_1,...,V_n, where each V_i={1,...,r}. Denote the j-th vertex of V_i by (i,j). We want to choose vertices (1,j_1),...,(n,j_n) such that the total number of paths in the induced graph is polynomial in n. Given the structure of G, a weaker though nontrivial result would be to show that no path in the induced graph has length greater than Clog(n) for every constant C.

We have the following structure on the original graph:

1) If i >= i' then (i,j) is not connected to (i',j') for all j,j'.

2) If (i,j) is connected to (i',j') and (i,k) connected to (i',k') then j=k.

3) If (i,j) is connected to (i',j') then (i,j) is connected to (i',k) for all k=1,...,j'.

4) If (i,j) is connected to (i',j') and (i',j') is connected to (i'',j'') then (i,j) is connected to (i'',j'').

Thanks. Go M-O!!