Local equivalence of transversals in matroids

D. Fon-Der-Flaass ^{∗} Mathematics Department, Queen Mary and Westfield College, London E1 4NS

                email: d.g.flaass@qmw.ac.uk

Submitted: May 21, 1996; Accepted: August 2, 1996.

Abstract Given any system of n subsets in a matroid M, a transversal of this system is an n-tuple of elements of M, one from each set, which is independent. Two transversals differing by exactly one element are adjacent, and two transversals connected by a sequence of adjacencies are locally equivalent, the distance between them being the minimum number of adjacencies in such a sequence. We give two sufficient conditions for all transversals of a set system to be locally equivalent. Also we propose a conjecture that the distance between any two locally equivalent transversals can be bounded by a function of n only, and provide an example showing that such function, if it exists, must grow at least exponentially.

Let M be a matroid, and V = (V_{1}, …, V_{n}) a collection of subsets of M. By a transversal of V we mean a sequence (v_{1}, …, v_{n}) of elements of M such that v_{i} ∈ V_{i} for i = 1, …, n, and v_{1}, …, v_{n} are independent. By the well-known Rado’s Theorem, transversals exist if and only if the following condition is satisfied:

For every X ⊆ {1, …, n}, rank ( ⋃_{i∈X} V_{i}) ≥ |X|.  (1)

We say that a transversal (v′_{1}, …, v′_{n}) is a (result of a) local replacement of (v_{1}, …, v_{n}) at i if v′_{j} = v_{j} for j ≠ i; and call two transversals locally equivalent if one can be obtained from the other by a sequence of local replacements; the length of the shortest such sequence being the distance between the transversals.

In this note we address two questions: under what conditions are all transversals of a collection V locally equivalent; and how big (in terms of n) can be the distance between two locally equivalent transversals. Also, we shall consider in more detail the case when M is the free matroid (the matroid having no cycles).

∗On leave from Institute of Mathematics, Novosibirsk, Russia; partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research.

1 Sufficient conditions of local equivalence

Here we shall prove two sufficient conditions for all transversals of a set system to be locally equivalent.

THEOREM 1 If a collection V = (V_{1}, …, V_{n}) of subsets of a matroid M is such that

For every ∅ ≠ X ⊆ {1, …, n}, rank ( ⋃_{i∈X} V_{i}) > |X|  (2)

then all transversals of V are locally equivalent.

The second theorem is a straightforward generalization of a result proved in [1]. Call a subset V of M thick if for every flat A of M either V ⊆ A, or |V ∩A| < |V |/2.

THEOREM 2 If V_{1}, …, V_{n} are thick subsets of M and V = (V_{1}, …, V_{n}) satisfies (1) then all transversals of V are locally equivalent, and the distance between any two of them does not exceed 2n − 1.

Some examples of thick subsets: one-element sets, cycles of size 3, subspaces of an n-dimensional vector space over GF(2).

A partial case of Theorem 2 for M a linear vector space over the field GF (2), and V_{i} one- or two-dimensional subspaces was proved in [1] and independently in [4]. The proof from [1], almost unchanged, applies to the general situation.

We use the notation ⟨X⟩ for X ⊆ M to mean the flat in M generated by X.

PROOF OF THEOREM 1.

Let \overline{x} = (x_{1}, …, x_{n}) and \overline{y} = (y_{1}, …, y_{n}) be two transversals of V = (V_{1}, …, V_{n}). Let D = D(\overline{x}, \overline{y}) = \{i | x_{i} ≠ y_{i}\}. We shall prove that \overline{x} and \overline{y} are locally equivalent by induction on d = |D(\overline{x}, \overline{y})|.

First we introduce some notation:

I = {1, …, n};

X_{J} = ⟨x_{j} | j ∈ J⟩ where J ⊆ I;

for v ∈ ⟨\overline{x}⟩, let I_{X}(v) be the smallest set J ⊆ I such that v ∈ X_{J}. (This set is uniquely determined.)

Suppose first that ⟨x_{1}, …, x_{n}⟩ ≠ ⟨y_{1}, …, y_{n}⟩. This means that y_{i} ∉ ⟨x_{1}, …, x_{n}⟩ for some i. Then the sequence \overline{x}′ = (x_{1}, …, x_{i−1}, y_{i}, x_{i+1}, …, x_{n}) is an independent transversal of V. It is a local replacement of \overline{x} at i; and |D(\overline{x}′, \overline{y})| < |D(\overline{x}, \overline{y})|. By induction, we are done in this case.

So, let X = ⟨x_{1}, …, x_{n}⟩ = ⟨y_{1}, …, y_{n}⟩. We construct inductively the sequence ∅ = I_{0} ⊆ I_{1} ⊆ … ⊆ I_{r} ⊆ I as follows:

I_{k+1} = I_{k} ∪ {j ∈ I \ I_{k} | V_{j} ⊈ X_{I\I_{k}}};

r is the first index for which I_{r} ∩ D ≠ ∅.

The property (2) implies that I_{k} ⊂ I_{k+1} for all 0 ≤ k < r; in particular, the length of the sequence does not exceed n − d + 1, and the number r is well-defined.

Now we construct a sequence (i_{1}, …, i_{r}) of indices, and a sequence (v_{1}, …, v_{r}) of elements v_{k} ∈ V_{i_{k}}; starting with i_{r} and v_{r}. Choose any i_{r} ∈ I_{r}∩D, and v_{r} ∈ V_{i_{r}} \X_{I\I_{r}}.

The choice of i_{r} and v_{r} implies that i_{r} ∈ I_{r} \ I_{r−1}, and that the set I_{X}(v_{r}) contains an element j ∈ I_{r−1} for which V_{j} ⊈ X_{I\I_{r−1}}. Set i_{r−1} = j, and choose v_{r−1} ∈ V_{j} \ X_{I\I_{r−1}}. Again we have i_{r−1} ∈ I_{r−1} \ I_{r−2}, and the set I_{X}(v_{r−1}) contains an element j ∈ I_{r−2} for which V_{j} ⊈ X_{I\I_{r−2}}. We continue in the same manner, and finally find i_{1} ∈ I_{1} and v_{1} ∈ V_{i_{1}} such that v_{1} ∉ ⟨X⟩.

To simplify the notation, let us assume that i_{1} = 1, …, i_{r} = r.

Now we shall perform certain local replacements of both \overline{x} and \overline{y}. Consider the sequences \overline{x}^{(i)} = (v_{1}, …, v_{i}, x_{i+1}, …, x_{n}) and \overline{y}^{(i)} = (v_{1}, …, v_{i}, y_{i+1}, …, y_{n}) for i = 1, …, r. Let also \overline{x}^{(0)} = \overline{x}, \overline{y}^{(0)} = \overline{y}.

By the choice of the elements v_{i}, we have v_{i} ∉ ⟨x_{i}, …, x_{n}⟩, and for i ≥ 2, v_{i} ∈ ⟨x_{i−1}, …, x_{n}⟩. Therefore all the sequences \overline{x}^{(j)}, 0 ≤ j ≤ r, are transversals, and are locally equivalent to \overline{x}.

If we have ⟨\overline{x}^{(i)}⟩ = ⟨\overline{y}^{(i)}⟩ for i = 1, …, j then all the sequences \overline{y}^{(i)}, 0 ≤ i ≤ j, are also transversals, and are locally equivalent to \overline{y}. If this holds for j = r then |D(\overline{x}^{(r)}, \overline{y}^{(r)})| = |D(\overline{x}, \overline{y})|−1, and \overline{x} and \overline{y} are locally equivalent by induction. On the other side, if i is the first value for which ⟨\overline{x}^{(i)}⟩ ≠ ⟨\overline{y}^{(i)}⟩ then \overline{x}^{(i)} is locally equivalent to \overline{y}^{(i)} by the argument from the beginning of this proof. Thus, in either case \overline{x} is locally equivalent to \overline{y}, and the theorem is proved. □

PROOF OF THEOREM 2.

The proof below exactly follows the proof of Proposition 5.1 in [1].

Take any two bases \overline{x} = (x_{1}, …, x_{n}) and \overline{y} = (y_{1}, …, y_{n}). Suppose that x_{i} ≠ y_{i} for some i. Let X = ⟨x_{j} | j ≠ i⟩, and Y = ⟨y_{j} | j ≠ i⟩. As x_{i} ∉ X and y_{i} ∉ Y, and using the fact that V_{i} is thick, we have

|V_{i} \ (X ∪ Y)| ≥ |V_{i}| − |V_{i} ∩ X| − |V_{i} ∩ Y | > |V_{i}| − |V_{i}|/2 − |V_{i}|/2 = 0.

Therefore there exists an element z of V_{i} which belongs to neither X nor Y; and we can replace both x_{i} and y_{i} by z. Thus, using at most two local replacements, we can reduce by 1 the number of places in which \overline{x} and \overline{y} disagree.

This argument gives an upper bound of 2n−1 on the maximum distance between transversals; because at the last stage, when \overline{x} and \overline{y} differ in only one place, one needs only one local replacement, and not two. □

The proof of Theorem 1 also gives an upper bound on the distance between transversals; the distance cannot exceed

2 + 4 + … + 2(n − 1) + 1 = n^{2} − n + 1.

By all probability, this bound is far from sharp. It would be very interesting to find the exact bound on the distance between transversals under the assumptions of Theorem 1.

2 Free matroid

A free matroid M is a matroid with no cycles. In a free matroid all subsets are independent; and rank (X) = |X| for all X ⊆ M. Let V = (V_{1}, …, V_{n}) be a collection of subsets of M which has at least one transversal. Let N = {1, …, n}. By the kernel of V we shall mean the largest subset X ⊆ N for which

| ⋃_{i∈X} V_{i}| = |X|.

The kernel exists since if X_{1} and X_{2} satisfy this property then so does X_{1} ∪ X_{2}.

THEOREM 3 Two transversals of V are locally equivalent if and only if they agree on the kernel K of V; the distance between them then does not exceed 2(n − |K|) − 1.

PROOF. We construct a bipartite graph G = (N ∪ M, E) with parts N and M; i ∈ N is adjacent to v ∈ M when v ∈ V_{i}. The transversals of V are in one-to-one correspondence with the matchings in G covering the part N; and a local replacement in this language corresponds to changing a single edge in the matching.

Let L be the set of vertices in M adjacent to vertices from K; by definition of K we have |L| = |K|. Thus, no edge incident to a vertex in K can ever be changed; and the “only if” part of the theorem is proved.

The set system corresponding to the graph induced on (N \ K) ∪ (M \ L) has an empty kernel, and at least one transversal. Thus, if K ≠ ∅ then we can apply induction on |N|. So we assume that K = ∅, i.e. V satisfies the conditions of Theorem 1.

Let A = (a_{i} | i ∈ N) and B = (b_{i} | i ∈ N) be any two transversals. Colour the edges (i, a_{i}) blue, and (i, b_{i}) red. The multigraph formed by all coloured edges is a disjoint union of cycles (possibly of length 2 if a_{i} = b_{i} for some i), paths, and isolated vertices. Let {C_{1}, …, C_{k}} be the set of all its cycles. We shall prove by induction on n + k that the distance between A and B is at most n + k. Since k ≤ n, and k = n only if A = B, this will prove the theorem.

Let C = ⋃ C_{i}, X = C ∩ N, Y = C ∩ M. We have |X| = |Y |. Applying the inequality 2 to the set X we see that in G there is an edge between X and M \ Y; colour it green. This edge is incident to exactly one of the cycles C_{1}, …, C_{k}; we delete it from C and apply the same argument to the set of remaining cycles; and continue in the same manner until we get k green edges. We shall consider the subgraph G′ of G formed by all coloured edges (blue, red, and green). The system corresponding to G′ also satisfies the property 2, and both A and B are its transversals.

Suppose first that there exists a green edge pq, p ∈ N, q ∈ M such that q is not incident to any red edge. Then we can perform one local replacement on B replacing the red edge incident to p by pq, and reduce the number of cycles by 1. By induction, we are done in this case. Similarly we treat the case when q is not incident to any blue edge.

Thus, for every green edge pq, q ∈ M the vertex q is incident to both red and blue edges. Let a be an end vertex of a red-blue path abc …; we have a ∈ M, b ∈ N, c ∈ M. Say, the edge ba is red, and bc is blue. No green edge is incident to a. We perform one local replacement on A, replacing bc by ba, and then delete the vertices b and a. The system corresponding to the remaining graph still satisfies the property 2, and has n − 1 sets. Thus, by induction, the theorem is proved. □

3 Lower bounds on the distance

We begin this section with a conjecture.

CONJECTURE. For every natural n there exists f(n) such that for every matroid M, if \overline{x} = (x_{1}, …, x_{n}) and \overline{y} = (y_{1}, …, y_{n}) are two locally equivalent transversals of a set system (V_{1}, …, V_{n}) in M then the distance between \overline{x} and \overline{y} does not exceed f(n).

I firmly believe this conjecture to be true. Trivially, f(1) = 1. It is easy to prove (and is left to the reader as an exercise) that f(2) = 3. The case n = 3 can possibly be dealt with by a long and tedious but not very difficult argument.

On the other hand, the function f(n) if it exists must grow at least exponentially. Below we shall construct examples proving this, and an example showing that f(3) ≥ 7.

EXAMPLE 1. Let M be a 3-dimensional space over any field; a, b, x three linearly independent vectors. Set

V_{1} = {a, b}, V_{2} = {a, b, x}, V_{3} = {a + x, b + x, a + b}.

It is easy to check that this set system has eight independent transversals, and that the transversals (a, b, a + x) and (b, a, b + x) are at distance 7.

EXAMPLE 2. For i = 1, …, n let V_{i} = {e_{i}^{0}, e_{i}^{1}} be n disjoint sets of size 2; M = ⋃ V_{i}, the matroid structure on M to be specified later.

The set H = V_{1} × … × V_{n} of n-tuples of elements of M forms the Hamming graph; two n-tuples being adjacent whenever they differ in only one coordinate. Every matroid structure on M determines a subgraph of H induced on the vertices corresponding to independent subsets of M; and we need to choose a matroid structure on M so that the diameter of some connected component of this graph be as big as possible. We shall use the following easy lemma.

LEMMA. For every set V, and every collection X of k-subsets of V such that |X_{1} \ X_{2}| ≥ 2 for any two different X_{1}, X_{2} ∈ X there exists a matroid on V in which a k-set is independent if and only if it doesn’t belong to X.

PROOF. Let the bases of the matroid be the k-subsets of V not belonging to X. We only need to check that they satisfy the exchange axiom:

For any two bases X, Y, and any x ∈ X there exists y ∈ Y such that X \{x}∪{y} is also a base.

If x ∈ Y then we can take y = x. If X \ Y = {x} then Y \ X = {y}, and we replace x by y. So, let x ∈ X \ Y, and |Y \ X| ≥ 2, say, {y, z} ⊆ Y \ X. By our assumption on the collection X at least one of the sets X \ {x} ∪ {y}, X \ {x} ∪ {z} does not belong to X and therefore is a base — the exchange property is proved. □

We shall denote vertices of H by (0, 1)-vectors of length n; the vector (ϵ_{1}, …, ϵ_{n}) corresponding to the transversal (e_{1}^{ϵ_{1}}, …, e_{n}^{ϵ_{n}}). The condition on the collection X from the Lemma now means simply that X corresponds to an independent set of vertices of H.

Let n be even, n = 2m. Denote by H_{i} the set of vectors of weight i: those having exactly i coordinates equal to 1.

We shall construct the set X = H_{m−2} ∪ (H_{m} \ Y) ∪ H_{m+2} for some Y ⊆ H_{m} such that in the graph H \ X the set Y is contained in a connected compomnent of large diameter.

We define a graph on the set H_{m}; two vectors are adjacent if and only if they differ in exactly two coordinates. This is the Johnson graph J(2m, m). The vertices of any induced path of length l in this graph form such set Y with the diameter of the connected component equal to 2l. So, we need to find long induced paths in the graphs J(2m, m). By a recent result of A.Evdokimov [2], one can find such paths of length > (2 − ϵ)^{n} for any ϵ > 0 and large enough n. This proves that f(n) grows faster than any exponent (2 − ϵ)^{n}.

The mentioned theorem of A.Evdokimov is new and yet unpublished but it is easy to prove an exponential (though worse) lower bound using a well-known result by the same A.Evdokimov [3] that in the binary Hamming graph of dimension m one can find an induced path of length c · 2^{m}. If (v_{1}, …, v_{l}) is such path then the sequence of vectors (w_{1}, …, w_{l}) where w_{i} = v_{i}\overline{v}_{i} (\overline{v}_{i} is the complement of v_{i}) gives an induced path in the graph J(2m, m) of the same length. Thus, f(n) ≥ c · 2^{n/2}.

Finally, I conjecture that f(n) ≤ 2^{n} − 1. This conjecture is not supported by any evidence, and is much more dubious than the first one.

References

[1] A. Bouchet, Digraph decompositions and Eulerian systems. SIAM J. Alg. Disc. Meth. 1987, vol.8, no.3, 323–337.

[2] A. Evdokimov, private communication.

[3] A. Evdokimov, The maximal length of a chain in the unit n-dimensional cube. Mat. Zametki 1969, vol.6, 309–319. [Russian; English transl.: Math. Notes 1969, vol.6, 642–648] [4] D. Fon-Der-Flaass, Local complementations of simple and oriented graphs,

Sibirskii Zhurnal Issledovanija Operacij 1994, vol.1, no.1, 43–62. [Russian; English transl. in: A.D.Korshunov (ed.), Discrete Analysis and Operations Research, Kluwer, 1996. 15–34]