Low weight perfect matchings (Q2223441): Difference between revisions

Summary: Answering a question posed by \textit{Y. Caro} et al. [``Graphs isomorphisms under edge-replacements and the family of amoebas'', Preprint, \url{arXiv:2007.11769}], we show that for every positive integer \(n\) and every function \(\sigma: E(K_{4n})\to\{-1,1\}\) with \(\sigma(E(K_{4n}))=0\), there is a perfect matching \(M\) in \(K_{4n}\) with \(\sigma(M)=0\). Strengthening the consequence of a result of \textit{Y. Caro} and \textit{R. Yuster} [Graphs Comb. 32, No. 1, 49--63 (2016; Zbl 1331.05098)], we show that for every positive integer \(n\) and every function \(\sigma: E(K_{4n})\to\{-1,1\}\) with \(|\sigma(E(K_{4n}))|<n^2+11n+2,\) there is a perfect matching \(M\) in \(K_{4n}\) with \(|\sigma(M)|\leqslant 2\). Both these results are best possible.