Farber's basis pair graph connectivity conjecture

Let MM be a matroid with ground set E(M)E(M) and rank r(M)r(M). Its basis pair graph G(M)G(M) has as vertices the ordered triples (A1,A2,A3)(A_1,A_2,A_3), where A1A_1 and A2A_2 are disjoint bases of MM and A3=E(M)(A1A2)A_3=E(M)-(A_1\cup A_2). Two vertices are adjacent when they differ by switching a pair of elements in two different sets.

Farber's conjecture. The basis pair graph of any matroid is connected.

This conjecture was posed by M. Farber, who proved it for transversal matroids; the source also notes results for graphic and cographic matroids. It remains open in general.

Sources & referencesView supporting material

Primary source

Joseph E. Bonin, “Sparse paving matroids, basis-exchange properties, and cyclic flats”, arXiv:1011.1010 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.