9
$\begingroup$

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:

  1. What are necessary and sufficient conditions for the existence of a distinguished matching?
  2. In the event that such a matching exists is there an efficient algorithm to find such a matching?
  3. 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.

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ How do you rule out the possibility that $DY = \{ y_1 \} $ and $DX = \{ x_1,x_2,x_3 \} $ with edges $(x_i,y_1)$ for $i=1,2,3$? I guess I must be missing something? Thanks! $\endgroup$
    – Patricia Hersh
    Commented Oct 23, 2012 at 13:41
  • 5
    $\begingroup$ Is there a typo or am I missing something? The first condition doesn't involve DY, and the second one is always satisfied when DY is empty or a singleton, so they can't possibly imply that |DX| = |DY|. $\endgroup$
    – Johan Wästlund
    Commented Oct 23, 2012 at 13:46
  • $\begingroup$ Patricia and Johan, thank you for your comments which are absolutely correct. I have adjusted the definition and I hope everything now makes sense. $\endgroup$
    – Nick Gill
    Commented Oct 24, 2012 at 8:49
  • 1
    $\begingroup$ Patricia’s example satisfies the adjusted definition as well. $\endgroup$
    – Emil Jeřábek
    Commented Oct 24, 2012 at 10:32
  • 1
    $\begingroup$ heck, i've not made a very good job of this - sorry! i'm going to have another go in a moment at writing down all of the required conditions. my aim was to have as few as possible, so that the definition did not become hideous, but i have overdone it... $\endgroup$
    – Nick Gill
    Commented Oct 24, 2012 at 12:09

1 Answer 1

Reset to default
1
$\begingroup$

Answering one's own question is a bit weird, but I think I might now understand what is going on here...

Define a new graph $\mathcal{H}$ whose vertices are the elements of $Y$. Connect two vertices $y_1, y_2 \in Y$ if they have a common neighbour in $X$.

Observe that elements of $X$ correspond to maximal cliques in the new graph $\mathcal{H}$. The subset $DX$ corresponds to a set of maximal cliques that cover all of the vertices of $\mathcal{H}$. Thus $|DX|$ must be at least as big as the clique cover number of $\mathcal{H}$.

Observe next that $DY$ is a set of vertices of $\mathcal{H}$ which are all pairwise disconnected. Thus $DY$ is an independent set.

It is clear that the clique cover number of a graph is always at least the independence number of the graph. Now the requirement that $|DX|=|DY|$ implies that the clique cover number of $\mathcal{H}$ is the same as the size of a maximal independent set (the independence number) of $\mathcal{H}$.

Thus we are in an extremal situation. What is more this situation has been discussed elsewhere on MathOverflow. The rest of this answer is a summary of the answers given in the other MO thread...

The condition that our graph $\mathcal{H}$ has coinciding clique cover number and independence number is equivalent to the condition that the complement graph $\mathcal{H}'$ has coinciding chromatic and clique numbers.

This latter condition seems difficult, however a definition from the literature is relevant here: a perfect graph is one in which the chromatic number of every induced subgraph equals the clique number of that subgraph. A characterization of perfect graphs exists: perfect graphs are the same as Berge graphs.

The proof of this characterization is known as the Strong Perfect Graph Theorem. This theorem is a very big deal, and its tremendous difficulty is enough to make one think that characterising graphs with the weaker condition of coinciding chromatic and clique numbers is likely to be nigh on impossible.

(I'll wait and see how people respond to this before I accept my own answer! Many thanks to the people who commented and forced me to get my question right in the first place.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .