Data vector expressibility

Let $G = (X \cup Y, E)$ be a bipartite multigraph. We proceed by induction on $|E|$. If $|E| = 0$, then we are trivially done. Assume that $|E| \geq 1$. Let $\Delta$ denote the maximum degree of $G$. Let $e \in E$ be an arbitrary edge, and let $x \in X$ and $y \in Y$ be its endpoints. Let $G' = (X \cup Y, E')$ be the graph obtained by removing $e$ from $G$. As the maximum degree of $G'$ is at most $\Delta$, by induction hypothesis, there is an edge coloring $f' \colon E' \to [1..\Delta]$ of $G'$.

Since $\mathrm{deg}_{G'}(x), \mathrm{deg}_{G'}(y) < \Delta$, there exist $i, j \in [1..\Delta]$ such that vertex $x$ is not incident with an $i$-edge in $f'$, and likewise for $y$ and $j$. If $i = j$, then we are done by coloring $e$ with $i$. So, assume $i \neq j$. Without loss of generality, we assume that $x$ is incident with a $j$-edge in $f'$, as otherwise we could have set $i = j$.

We construct a path. Let us start in $x_0 = x$ and take a ${\color{magenta}j}$-edge $e_1 \in E'$ going to some vertex $v_1$. If $e_1$ is incident with an ${\color{blue}i}$-edge $e_2 \in E'$, then we take it and move to some vertex $v_2$. We continue this process alternating with ${\color{magenta}j}$-edges and ${\color{blue}i}$-edges. Since $f'$ is an edge coloring, a vertex $v$ cannot repeat along this path, as otherwise $v$ would be incident with two edges of the same color. Thus, we may obtain a maximal simple path $P$ of the form

$$v_0 \xrightarrow{\color{magenta}e_1} v_1 \xrightarrow{\color{blue}e_2} v_2 \xrightarrow{\color{magenta}e_3}\ \cdots\ v_n, \text{ where } v_i \in X \text{ iff } i \text{ is even}.$$

By assumption on $x$, we have $n \geq 1$. Let $g' \colon E' \to [1..\Delta]$ be obtained from $f'$ by swapping ${\color{blue}i}$ and ${\color{magenta}j}$ on the edges of $P$. Note that $g'$ is an edge coloring.

Click for a proof.

For the sake of contradiction, suppose that some vertex $u$ is incident to two edges of the same color $k$ in $g'$. We must have $u = v_\ell$ for some $\ell \in [0..n]$ and $k \in \{{\color{blue}i}, {\color{magenta}j}\}$. We cannot have $\ell = 0$, as $v_0 = x$ is not incident to an ${\color{blue}i}$-edge in $f'$. We cannot have $1 \leq \ell < n$, as we swapped the occurrences of the two colors. We cannot have $\ell = n$ as otherwise we could have extended $P$ to a longer path.

Recall that $y$ is not incident to a ${\color{magenta}j}$-edge in $f'$. Thus, if $y$ appeared along $P$, we would have $v_n = y$ with $n$ even, which is impossible as $G$ is bipartite. Thus, $x$ is the first vertex of $P$, and $y$ does not appear along $P$. Consequently, in the edge coloring $g'$, neither $x$ nor $y$ is incident to a ${\color{magenta}j}$-edge.

Let $g \colon E \to [1..\Delta]$ be $g'$ extended with $g(e) = {\color{magenta}j}$. We are done since $g$ is an edge coloring of $G$.

$\Rightarrow$) Let $n$ be the number of transversals of the perfect matching. Since each element of $X_i$ must belong to exactly one transversal, we must have $|X_1| = \cdots = |X_k| = n$. Let $d \in \mathbb{D}$. Each transversal contains at most one occurrence of $d$. As there are $n$ transversals, this means that $X_1(d) + \ldots + X_k(d) \leq n$.

$\Leftarrow)$ Let $U = [1..k]$, and let $V \subseteq \mathbb{D}$ be the finite subset of colors occurring at least once in some $X_i$. Let $G = (U \cup V, E)$ be the bipartite multigraph where there are $X_i(d)$ edges of the form $\{i, d\}$. By assumption, we have $\mathrm{deg}(u) = n$ for each $u \in U$, and $\mathrm{deg}(v) \leq n$ for each $v \in V$. Thus, the maximum degree of $G$ is $n$, and hence its edge chromatic number is $n$ by Theorem 1.

Let $f \colon E \to [1..n]$ be an edge coloring of $G$. For every $i \in [1..n]$ and $j \in [1..k]$, let $e_{i,j}$ be the unique edge adjacent with vertex $j \in U$ such that $f(e_{i, j}) = i$. Let $d_{i, j} \in V$ be the other vertex adjacent with $e_{i, j}$. Since $f$ is an edge coloring, the tuple $t_i = (d_{i, 1}, \ldots, d_{i, k})$ is a transversal. Thus, $T = \{\!\!\{t_1, \ldots, t_n\}\!\!\}$ is a perfect matching.

$\Rightarrow$) By assumption there exist injections $\iota_1, \ldots, \iota_n \colon \mathit{Vars} \to \mathbb{D}$ satisfying $\bm{v} = \sum_{j \in [1..n]} \bm{a}_{\iota_j}$. Let $X_i \colon \mathbb{D} \to \N$ be defined by $X_i(d) = |\{\!\!\{j \in [1..n] : \iota_j(x_i) = d\}\!\!\}|$. For every $d \in \mathbb{D}$, we have

$$\bm{v}(d) = \sum_{i \in [1..k]} X_i(d) \cdot \bm{a}(x_i).$$

For each $i \in [1..n]$, let $t_i = (\iota_i(x_1), \ldots, \iota_i(x_k))$. By injectivity of $\iota_i$, the tuple $t_i$ is a transversal. Thus, by definition, $\{\!\!\{t_1, \ldots, t_n\}\!\!\}$ is a perfect matching of $X_1, \ldots, X_k$.

$\Leftarrow$) Let $T$ be a perfect matching for $X_1, \ldots, X_k$. For each $t \in T$, let $\iota_t(x_i) = t[i]$. Since $t$ is a transversal, $\iota_t$ is an injection. For every $d \in \mathbb{D}$, we have

$$\begin{aligned} \sum_{t \in T} \bm{a}_{\iota_t}(d) &= \sum_{i \in [1..k]} |\{\!\!\{t \in T : \iota_t(x_i) = d\}\!\!\}| \cdot \bm{a}(x_i) \\ &= \sum_{i \in [1..k]} |\{\!\!\{t \in T : t[i] = d\}\!\!\}| \cdot \bm{a}(x_i) \\ &= \sum_{i \in [1..k]} X_i(d) \cdot \bm{a}(x_i) && (\text{by $X_i = \{\!\!\{t[i] : t \in T\}\!\!\}$}). \end{aligned}$$

Recall that $\bm{v}(d) = \sum_{i \in [1..k]} X_i(d) \cdot \bm{a}(x_i)$. Hence, we have $\bm{v} = \sum_{t \in T} \bm{a}_{\iota_t}$, and so $\bm{v} \in \langle \bm{a} \rangle$.

We have $\bm{v} \in \langle A \rangle$ iff $\bm{v} = \bm{v}_1 + \ldots + \bm{v}_m$ for some $\bm{v}_1 \in \langle \bm{a}_1 \rangle, \ldots, \bm{v}_m \in \langle \bm{a}_m \rangle$. Thus, by Proposition 3 and Lemma 2, we have $\bm{v} \in \langle A \rangle$ iff there exist $n_1, \ldots, n_m \in \N$ and finite multisets $X_{1, 1}, \ldots, X_{m, k} \colon \mathbb{D} \to \N$ satisfying Item 1 of the claim.

It remains to prove Item 2, i.e. that the number of colors can be bounded. Let us pick a solution minimizing the size of $S = \mathrm{supp}(X_{1, 1} + \ldots + X_{m, k})$. Let us show that $|S| \leq m(2k-1) + |\mathrm{supp}(\bm{v})| + 1$.

We say that $d \in \mathbb{D}$ is $i$-dominant if $X_{i, 1}(d) + \ldots + X_{i, k}(d) > n_i / 2$. Let $D_i$ denote the set of $i$-dominant colors. We have $|D_i| < 2k$, as otherwise we would obtain this contradiction:

$$k n_i = \sum_{j \in [1..k]} |X_{i, j}| = \sum_{j \in [1..k]} \sum_{d \in \mathbb{D}} X_{i, j}(d) \geq \sum_{d \in D_i} \sum_{j \in [1..k]} X_{i, j}(d) > \sum_{d \in D_i} n_i / 2 \geq k n_i.$$

We say that a color is non-dominant if it is not $i$-dominant for any $i \in [1..m]$. For the sake of contradiction, suppose that $|S| \geq m(2k-1) + |\mathrm{supp}(\bm{v})| + 2$. By the pigeonhole principle, there exist distinct non-dominant colors $e, e' \in S$ not appearing in $\mathrm{supp}(\bm{v})$.

We merge color $e'$ into color $e$ by defining

$$\begin{aligned} X_{i, j}'(e') &= 0, \\ X_{i, j}'(e) &= X_{i, j}(e) + X_{i, j}(e'), \\ X_{i, j}'(f) &= X_{i, j}(f) && \text{for all } f \notin \{e, e'\}. \end{aligned}$$

Observe that $X_{1,1}', \ldots, X_{m,k}'$ satisfy Item 1 of the claim, namely:

• $\bigwedge_{d \in \mathbb{D}} \bm{v}(d) = \sum_{i \in [1..m], j \in [1..k]} X_{i, j}'(d) \cdot \bm{a}(x_j)$ holds since $e, e' \notin \mathrm{supp}(\bm{v})$;

• $|X_{i, j}'| = |X_{i, j}| = n_i$;

• $\bigwedge_{i \in [1..m], d \in \mathbb{D}} \sum_{j \in [1..k]} X_{i, j}(d) \leq n_i$ holds since $e$ and $e'$ are non-dominant.

This contradicts the minimality of $S$ since $S' = \mathrm{supp}(X_{1,1}' + \ldots + X_{m,k}') = S \setminus \{e'\}$.

Theorem 4 yields a system of linear inequalities for which at most polynomially many colors are needed. Thus, expressibility reduces to integer linear programming feasability.