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.)
- 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!
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.
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.