Clique game (original) (raw)
The clique game is a positional game where two players alternately pick edges, trying to occupy a complete clique of a given size. The game is parameterized by two integers n > k. The game-board is the set of all edges of a complete graph on n vertices. The winning-sets are all the cliques on k vertices. There are several variants of this game: The clique game (in its strong-positional variant) was first presented by Paul Erdős and John Selfridge, who attributed it to Simmons. They called it the Ramsey game, since it is closely related to Ramsey's theorem (see below).
| Property | Value |
|---|---|
| dbo:abstract | The clique game is a positional game where two players alternately pick edges, trying to occupy a complete clique of a given size. The game is parameterized by two integers n > k. The game-board is the set of all edges of a complete graph on n vertices. The winning-sets are all the cliques on k vertices. There are several variants of this game: * In the strong positional variant of the game, the first player who holds a k-clique wins. If no one wins, the game is a draw. * In the Maker-Breaker variant , the first player (Maker) wins if he manages to hold a k-clique, otherwise the second player (Breaker) wins. There are no draws. * In the Avoider-Enforcer variant, the first player (Avoider) wins if he manages not to hold a k-clique. Otherwise, the second player (Enforcer) wins. There are no draws. A special case of this variant is Sim. The clique game (in its strong-positional variant) was first presented by Paul Erdős and John Selfridge, who attributed it to Simmons. They called it the Ramsey game, since it is closely related to Ramsey's theorem (see below). (en) |
| dbo:wikiPageID | 58943723 (xsd:integer) |
| dbo:wikiPageLength | 4244 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1069428355 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:John_Selfridge dbr:Paul_Erdős dbr:Positional_game dbr:Complete_graph dbc:Positional_games dbr:Clique_(graph_theory) dbr:Maker-Breaker_game dbr:József_Beck dbr:Strategy-stealing_argument dbr:Avoider-Enforcer_game dbr:Ramsey's_theorem dbr:Sim_(pencil_game) dbr:Strong_positional_game |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Positional_games |
| rdfs:comment | The clique game is a positional game where two players alternately pick edges, trying to occupy a complete clique of a given size. The game is parameterized by two integers n > k. The game-board is the set of all edges of a complete graph on n vertices. The winning-sets are all the cliques on k vertices. There are several variants of this game: The clique game (in its strong-positional variant) was first presented by Paul Erdős and John Selfridge, who attributed it to Simmons. They called it the Ramsey game, since it is closely related to Ramsey's theorem (see below). (en) |
| rdfs:label | Clique game (en) |
| owl:sameAs | wikidata:Clique game https://global.dbpedia.org/id/9RSmu |
| prov:wasDerivedFrom | wikipedia-en:Clique_game?oldid=1069428355&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Clique_game |
| is dbo:wikiPageRedirects of | dbr:Ramsey_game |
| is dbo:wikiPageWikiLink of | dbr:Positional_game dbr:Frank_Ramsey_(mathematician) dbr:Clique_(graph_theory) dbr:Maker-Breaker_game dbr:Ramsey_game |
| is foaf:primaryTopic of | wikipedia-en:Clique_game |