Question about some properties of combinatorial structures

62 Views Asked by At

Consider $\mathcal A$ as the set of perfect matchings in the complete bipartite graph $K_{n,n}$ and let $i$ be an edge of $K_{n,n}$. Let $$ B_i=\{a\in \mathcal A: \hbox{matching }a\hbox{ has edge }i\}. $$ Clearly $\frac{|\mathcal A|}{|B_i|}=\frac{n!}{(n-1)!}=n$, which is $poly(n)$ and which is independent of $i$.

I have the following question: For which combinatorial structures (other than perfect matchings) it holds that $\frac{|\mathcal A|}{|B_i|}$ is independent of $i$? Is there any name for this property?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $K_{n,n}$ be the complete bipartite graph with left vertex set $a_j, j=1,\ldots,n$ and right vertex set $b_j, j=1, \ldots, n$. There is a 1-1 correspondence between perfect matchings in $K_{n,n}$ and permutations in $S_n$. For example, the set of perfect matchings that contain the edge $(a_i,b_j)$ corresponds to the set of permutations in $S_n$ that map element $i$ to element $j$. It's clear this set has $(n-1)!$ permutations.

In general if a group $G$ acts transitively on a set $X$ of cardinality $n$, then the set of elements in the group that map an element $i$ to an element $j$ in $X$ has the same cardinality as the set of elements in the group that map the element $i$ to itself, and this cardinality is equal to $|G|/|X|=|G|/n$ due to the orbit-stabilizer lemma. Thus, $|G|$ divided by $|G|/|X|$ equals $|X|=n$, which happens to be polynomial in $n$.

Since $S_n$ is 2-transitive, the set of permutations in $S_n$ that map $i_1,i_2$ to $j_1,j_2$, respectively, is $(n-2)$!, and the ratio of $|S_n|$ to this quantity is a quadratic, hence also a polynomial in $n$. This corresponds to the number of perfect matchings in $K_{n,n}$ that contain a chosen set of two independent edges.