The permanent conjecture

Importance: Medium ✭✭
Author(s): Kahn, Jeff
Subject: Combinatorics
» Matrices
Recomm. for undergrads: no
Prize: none
Posted by: mdevos
on: March 8th, 2007

\begin{conjecture} If $A$ is an invertible $n \times n$ matrix, then there is an $n \times n$ submatrix $B$ of $[A A]$ so that $perm(B)$ is nonzero. \end{conjecture}

If true, this conjecture would imply the \OPref[nowhere-zero point in a linear mapping conjecture]{a_nowhere_zero_point_in_a_linear_mapping} via the Alon-Tarsi polynomial technique. I believe Yang Yu was the first to suggest the following generalization of the permanent conjecture.

\begin{conjecture}[Yu] If $A,B$ are invertible $n \times n$ matrices over the same field, then there is an $n \times n$ submatrix $C$ of $[A B]$ so that $perm(C)$ is nonzero. \end{conjecture}

This conjecture when restricted to the field ${\mathbb Z}_3$ is a consequence of the Alon-Tarsi basis conjecture. In addition to implying the above conjecture, the truth of this conjecture for matrices over the field ${\mathbb Z}_3$ would imply that every 6-edge-connected graph has a nowhere-zero 3-flow, thus resolving \OPref[The weak 3-flow conjecture]{3_flow_conjecture}.