Graph Theory: problem with an n-partite graph

Question

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!!

Answer 1

The result appears to be false for $r=1$. It's not immediately obvious whether the counterexample extends even to $r=2$.

First, a (hopefully accurate) restatement of the conditions on $G$. The directed graph $G$ has vertex set $[n]\times[r]$, which we think of as embedded in the plane in the usual way for the purposes of restating conditions (1)–(4):

1. All edges in $G$ are directed right to left.
2. For each pair of columns, at most one vertex of the first column sends edges to the second.
3. The neighbourhood of each vertex is a down-set (consisting of initial segments, possibly empty, of each column).
4. $G$ is transitive.

For $r=1$, the complete graph with all edges oriented right to left satisfies these properties, and the only possible induced graph is $G$ itself, which has almost $2^n$ paths.

For higher $r$, one approach to searching for counterexamples is to try and weave together complete transitive graphs, but conditions 2 and 4 mean you need to keep them well separated, and condition 3 tends to force them to collide if you try to avoid leaving large gaps.

Answer 2

Yes, I forgot to mention that the statement is known to be false for r=1, and the result in complexity theory I'm going for is known to be true when r=log(n). Though it is proved with different methods entirely, so even a positive answer when r=log(n) would be interesting. Personally, I believe it is true for r=2, but have resigned myself to attempting to prove it assuming that $r\in\omega(1)$ for the time being.