Suppose I have a bipartite graph on a pair of vertex sets $X$ and $Y$.

Definition: A *distinguished matching* is a subset $DX\subseteq X$ and a subset $DY\subseteq Y$ such that:

- For all $y\in Y$, there exists at least one $x\in DX$ such that $(x,y)$ is an edge. (We say that
*$DX$ covers Y'*); - For all $x\in X$, there exists at most one $y\in DY$ such that $(x,y)$ is an edge. (We say that
*$DY$ is distinguished'*); - For all $x\in DX$ there exists a unique $y\in DY$ such that $(x,y)$ is an edge, and for all $y\in DY$ there exists a unique $x\in DX$ such that $(x,y)$ is an edge. (We say that
*$DX$ and $DY$ are matched'*).

(**Note**: The third condition has been changed twice. I hope it's now correct.)

Questions:

- What are necessary and sufficient conditions for the existence of a distinguished matching?
- In the event that such a matching exists is there an efficient algorithm to find such a matching?
- The term `distinguished matching' is my own. Perhaps this notion has been studied by graph theorists under another name. If so, please give me some references!

Applications:

Suppose that $Y$ is the set of elements of some group $G$, and suppose that $X$ is the set of maximal abelian subgroups of $G$. An edge $(x,y)$ is drawn if the element $y$ is contained in the subgroup $x$. Suppose there is a distinguished matching. Then the set $DX$ is a minimally-sized cover of $G$ by abelian subgroups; the set $DY$ is a maximally-sized set of pairwise non-commuting elements.

It is easy to see that a minimal cover by abelian subgroups must be at least as big as a maximal set of pairwise non-commuting elements. The extremal situation is when they're the same size and that's what a matching yields.

Finite groups admitting such a matching include rank 1 groups of Lie type. Finite groups that don't admit such a matching include $Sym(n), n\geq 15$.

There are other group-theoretic variations on this idea: just change the adjectives *abelian* and *non-commuting* in the set-up.

Credits:

These type of coverings have been studied in group theory at various times. I came across them in joint work with A. Azad and J. Britnell. I'm mainly interested in the situation where the graph is finite, but any thoughts would be welcome.

5more comments