Matrix choosability
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).
- A nowhere-zero point in linear mappings
- Additive bases of vector spaces over prime fields
- Colorings and orientations of graphs
- Combinatorial Nullstellensatz
- Edge-Disjoint Spanning Trees of Finite Graphs
- Flows and generalized coloring theorems in graphs
- Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
- scientific article; zbMATH DE number 524118 (Why is no real title available?)
- Minimum partition of a matroid into independent subsets
- The permanent rank of a matrix
- Additive bases and flows in graphs
- Essential positive covers of the cube
- A matrix-valued Choquet–Deny theorem
- Additive bases and flows in graphs
- Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices
- Hyperplane covers of finite spaces and applications
- Alon-Tarsi for hypergraphs
- Subset selection for matrices
This page was built for publication: Matrix choosability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1976325)
