Generalized exponents of primitive, nearly reducible matrices (Q2761062)

A primitive non-negative matrix \(A\) induces a digraph \(D(A)\) and such digraphs are also called primitive. The correspondence between \(A\) and \(D(A)\) turns nearly reducible non-negative matrices to minimally strong digraphs (a matrix is nearly reducible if every replacement of a non-zero entry by zero yields a reducible matrix). For a digraph \(\Gamma \) define \(f(\Gamma ,k)\) and \(F(\Gamma ,k)\) as the minimum and maximum, respectively, of \(\exp_\Gamma (X)\), where \(X\) runs through all \(k\)-element sets of vertices and \(\exp_\Gamma (X)\) denotes the smallest \(p\) such that for each vertex \(i\) there exists a walk of length \(p\) that starts from \(X\) and ends at \(i\). The author defines a certain digraph \(D_{n-2}\) with \(n\) vertices, computes \(f(D_{n-2},k)\) and \(F(D_{n-2},k)\), proves that for every \(\Gamma \), \(\Gamma \) a primitive minimally strong digraph on \(n\) vertices, \(F(\Gamma ,k) \leq F(D_{n-2},k)\) holds, conjectures \(f(\Gamma ,k) \geq f(D_{n-2},k)\), and proves the conjecture for \(k \in \{1,n-2,n-1,n\}\).