Trace equivalence and a triple-overlap obstruction
Statement
Conjecture 6.5. 3. Form a digraph from the matrices A1,..., A t by putting t + 1 copies of the vertex set V in a row, connecting copy k of v to copy k + 1 of v with a horizontal edge for all vertices v and all k, and then from copy k to copy k + 1 put in the edge from copy k of vi to copy k + 1 of
vj precisely when aij = 1 in matrix Ak for k = 1,..., t. The question now is whether there exists a vertex u so that there is a non-trivial (i.e. not all horizontal edges) path from copy
1 of u to copy t + 1 of u.4. If we "squish" all the bipartite graphs from the previous items so they live on a single copy of V, marking edges from copy i to copy i + 1 with color i, then we have the sum of the (colored) outdegrees at each vertex is at least n, and we're asking for a non-trivial rainbow cycle which has the colors appearing in increasing order.
For a matrix A, the spectral radius of A is defined to be max {| λ|: λ an eigenvalue of A}.8
Record
- Source
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.