A matching game (Q1182968): Difference between revisions

A two-person game on \(K_{n,n}\) is introduced and studied in this paper. Two players, maker and breaker, alternatively take a previously untaken edge from \(K_{n,n}\). The game continues until all edges of \(K_{n,n}\) have been taken. Let \(G(M)\) be the subgraph of \(K_{n,n}\) induced by all edges taken by the maker and \(m(M)\) be the number of perfect matchings in \(G(M)\). The maker's aim is to make \(m(M)\) big and the breaker's is to force it small. It is proved that for any given \(s>0\), there is \(N(s)\), such that if \(n\geq N(s)\), then the maker has a strategy to guarantee \(m(M)\geq(1/2-s)^ n\).