Additive Bases and Flows in Graphs
Louis Esperet, Rémi de Joannis de Verclos, Tien-Nam Le, Stéphan Thomassé · SIAM Journal on Discrete Mathematics · 2018
It was conjectured by Jaeger et al. in 1992 that for any prime number $p$, there is a constant $c$ such that for any $n$, the union (with repetition) of the vectors of any family of $c$ linear bases of $\mathbb{Z}_p^n$ forms an additive basis of $\mathbb{Z}_p^n$ (i.e., any element of $\mathbb{Z}_p^n$ can be expressed as the sum of a subset of these vectors). In this note, we prove this conjecture when each vector contains at most two nonzero entries. As an application, we prove several results on flows in highly edge-connected graphs, extending known results. For instance, assume that $p\geqslant 3$ is a prime number and $\vec{G}$ is a directed, highly edge-connected graph in which each arc is given a list of two distinct values in $\mathbb{Z}_p$. Then $\vec{G}$ has a $\mathbb{Z}_p$-flow in which each arc is assigned a value of its own list.