Perfect matchings and derangements on graphs

Autor:	Bucic, Matija, Devlin, Pat, Hendon, Mo, Horne, Dru, Lund, Ben
Rok vydání:	2019
Předmět:	Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	We show that each perfect matching in a bipartite graph $G$ intersects at least half of the perfect matchings in $G$. This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph, and in terms of derangements and permutations on graphs. We give several related results and open questions.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1906.05908 Zobrazit plný text záznamu View this record from Arxiv