Matrix choosability (Q1976325)

Let \(F\) be a field and let \(\alpha= (\alpha_1,\dots, \alpha_m)\) and \(\beta= (\beta_1,\dots, \beta_n)\) be sequences of nonnegative integers. Suppose that subsets \(X_1,\dots, X_m\subseteq F\) and \(Y_1,\dots, Y_n\subseteq F\) have \(|X_i|\geq \alpha_i\) and \(|Y_j|\leq \beta_j\) for all \(i\), \(j\). Then a matrix \(A\) is \((\alpha, \beta)\)-pliant if there are vectors \(x\in X_1\times\cdots\times X_m\) and \(y\in F\setminus Y_1\times\cdots\times F\setminus Y_n\) with \(Ax= y\). To state the main theorem, we need several further definitions. A generalized permanent \(P_k(B)\) of an \(n\times n\) square matrix \(B\) is \[ P_k(B)= {1\over (k!)^n}\text{ perm}(B\otimes J_k), \] where \(k<\text{char}(F)\) if \(F\) has positive characteristic, and \(J_k\) is the \(k\times k\) matrix with all entries 1. Suppose that \(F\) has positive characteristic \(p\). Let \(w_1,\dots, w_t\in \{0,\dots, p-1\}\), and let \(I_0,\dots, I_t\subseteq \{1,\dots, n\}\) and \(J_1,\dots, J_t\subseteq \{1,\dots, m\}\) be such that \(|I_k|=|J_k|\) for all \(k\). (The two usages of \(J_k\) cause no confusion.) Further, let \(\chi^n_{I_k}\in F^n\) be the characteristic vector of \(I_k\), and define \(\chi^m_{J_k}\) similarly. Put \(\beta= \sum^t_{k=0} (w_k p^k)\chi^n_{I_k}\) and \(\alpha= (1,\dots, 1)+ \sum^t_{k=0} (w_k p^k)\chi^m_{J_k}\). Given an \(n\times m\) matrix \(A\), let \(A[I_k\mid J_k]\) be the square submatrix of \(A\) formed by the common entries of rows indexed by \(I_k\) and columns indexed by \(J_k\). The main result is the following: if \(P_{w_k}(A[I_k\mid J_k])\neq 0\) for all \(0\leq k\leq t\), then \(A\) is \((\alpha, \beta)\)-pliant. A weaker version of this result is given for characteristic 0. The author discusses how his result relates to previous results and conjectures, and gives several consequences that arise from particular choices of the sets \(I_k\), \(J_k\). For example, let \(G\) be a directed 3- or 4-edge connected graph, and for each edge \(e\), let \(\ell_e\) be a subset of \(\mathbb{Z}^k_p\). Then there is a flow \(\phi\) on \(G\) with \(\phi(e)\in \ell_e\) for all \(e\) provided \(|\ell_e|\) is at least \((p- 1)(p^{k- 1}+ p^{k- 2})+ 1\) (3-connected) or \((p- 1)p^{k- 1}+ 1\) (4-connected).