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.