Low Weight Perfect Matchings

Abstract

Answering a question posed by Caro, Hansberg, Lauri, and Zarb, we show that for every positive integer $n$ and every function $\sigma :E(K_{4n})\to \{-1,1\}$ with $\sigma \left(E(K_{4n})\right)=0$, there is a perfect matching $M$ in $K_{4n}$ with $\sigma (M)=0$. Strengthening a result of Caro and Yuster, we show that for every positive integer $n$ and every function $\sigma :E(K_{4n})\to \{-1,1\}$ with $\left|\sigma \left(E(K_{4n})\right)\right|<n^2+11n+2,$ there is a perfect matching $M$ in $K_{4n}$ with $|\sigma (M)|\le 2$. Both these results are best possible.