Let $G$ be a bipartite graph, $L$ ($R$) be the set of vertices in the left (right) part. Consider a graph $T$ with the set of vertices $R \times L$ ( $L \times R$ ) in the left (right) part. For any $l_1,l_2 \in L$, $r_1, r_2 \in R$, vertices $(r_1,l_1)$ and $(l_2,r_2)$ are adjacent in $T$ iff $l_1$ and $r_2$ are adjacent in $G$ and $l_2$ and $r_1$ are adjacent in $G$. Then $T$ has an automorphism $F$: For any $l \in L$, $r \in R$, $F((r,l))=(l,r), F((l,r))=(r,l)$. It seems that if $T$ has any perfect matching, then $T$ has a perfect matching invariant under $F$. Any ideas on how to prove this?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Not sure if this helps at all with your conjecture, but is it correct that the adjacency matrix of $T$ is the tensor square of the adjacency matrix of $G$? $\endgroup$– Sam HopkinsCommented Aug 13 at 3:21
-
1$\begingroup$ Okay, denoting by $M(G)$ the bipartite adjacency matrix of a bipartite graph $G$, it should actually be something like $M(T) = M(G) \otimes M(G)^t$, where $^t$ is transpose. $\endgroup$– Sam HopkinsCommented Aug 13 at 3:37
-
$\begingroup$ yes, that's correct, but I haven't been able to use it yet $\endgroup$– Fedor UshakovCommented Aug 13 at 8:15
Add a comment
|