Originators: Francois Jaeger, Matt DeVos (presented by Grace Work - REGS 2010)
Definitions: An m-by-n matrix A is (a,b)-choosable if whenever a-sets X1,...,Xn and b-sets Y1,...,Ym are chosen from F, there exist x ∈ X1×⋅⋅⋅×Xn and y ∈ Y1×⋅⋅⋅×Ym such that Ax = y.
Background: Every matrix is (1,|F|)-choosable, but when n=m a matrix is (|F|,1)-choosable if and only if it is invertible. The motivation for this problem comes from the study of nowhere-zero flows on graphs. When A is the incidence matrix of a directed graph G, an F-flow on G is a vector x such that Ax = 0. If we restrict the flows to be nonzero by specifying xj≠0, then the solution is a nowhere-zero F-flow. In the present context, we impose this requirement by specifying Xj=F-{0} for all j. Thus in the special case of incidence matrices, (|F|-1,1)-choosability is a stronger condition than the requirement of a nowhere-zero F-flow.
Conjecture 1 (Jeager): If F is a finite field with at least 4 elements, and A is an invertible n-by-n matrix with entries in F, then there exist x,y ∈ Fn satisfying Ax = y and having no coordinates equal to 0.
Comments: Alon & Tarsi [AT] proved Conjecture 1 for all fields not of prime order, using their polynomial technique.
Conjecture 2 (DeVos): If p is a prime, then every invertible matrix with entries in Zp is (k+2,p-k)-choosable for every k.
Comments: DeVos has no experimental evidence for this conjecture, so it may be false even for some small examples. He proved that every invertible matrix over a field F of characteristic 2 is (k+1,|F|-k)-choosable for every k.
Question 3: For special matrices, can (a,b)-choosability be guaranteed when a+b is smaller? For example, the matrix obtained from the incidence matrix of a directed tree by deleting one row is invertible. For which (a,b) and which fields is it (a,b)-choosable? Other special cases can also be studied.
References:
[AT] N. Alon, M. Tarsi, A nowhere-zero point in linear mappings,
Combinatorica 9 (1989), 393-395
[D] M. DeVos, Matrix choosability, J. Combinatorial Theory, Ser. A 90
(2000), 197-209