A matching game (Q1182968): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Xiao-Yun Lu / rank | |||
Property / author | |||
Property / author: Xiao-Yun Lu / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Van der Waerden and Ramsey type games / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Remarks on positional games. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Variations on a game / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a combinatorial game / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5514188 / rank | |||
Normal rank |
Latest revision as of 15:35, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A matching game |
scientific article |
Statements
A matching game (English)
0 references
28 June 1992
0 references
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\).
0 references
two-person game
0 references
matching
0 references