Biregular bipartite multigraphs and matchings in tensor products of bipartite graphs

Abstract

We answer a question of P. Higgins on permutations and involutions in binary arrays, arising in the study of regular finite semigroups. For a binary rectangular matrix M, we prove that if there is a permutation pi(x, y) = (f(x, y), g(x, y)) of its cells satisfying M(x, g(x,y)) = 1 for every cell, then there is an involution with the same property. The elementary proof places coins in the nonzero cells, reduces their support to a forest, and assigns consecutive integer weights to the coins incident to each row and column. We also prove a multiplicativity formula for bipartite expansion and a perfect matching theorem for tensor products of supports of matrices with prescribed margins. We study a stronger conjecture of F. Petrov on disjoint swaps in biregular bipartite multigraphs. We prove this conjecture for k = mn + eps, |eps| <= 2, and for n = 6, k = 6m + 3, and give a group-theoretic reformulation.