Strong games played on random graphs
In a strong game played on the edge set of a graph G there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of G (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a clique K[subscript k], a perfect ma...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
European Mathematical Information Service (EMIS)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110013 |
| _version_ | 1826194975830835200 |
|---|---|
| author | Ferber, Asaf Pfister, Pascal |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Ferber, Asaf Pfister, Pascal |
| author_sort | Ferber, Asaf |
| collection | MIT |
| description | In a strong game played on the edge set of a graph G there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of G (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a clique K[subscript k], a perfect matching, a Hamilton cycle, etc.). In this paper we consider strong games played on the edge set of a random graph G ∼ G(n, p) on n vertices. We prove that G ∼ G(n, p) is typically such that Red
can win the perfect matching game played on E(G), provided that p ∈ (0, 1) is a fixed constant. |
| first_indexed | 2024-09-23T10:04:48Z |
| format | Article |
| id | mit-1721.1/110013 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:04:48Z |
| publishDate | 2017 |
| publisher | European Mathematical Information Service (EMIS) |
| record_format | dspace |
| spelling | mit-1721.1/1100132022-09-30T18:48:39Z Strong games played on random graphs Ferber, Asaf Pfister, Pascal Massachusetts Institute of Technology. Department of Mathematics Ferber, Asaf In a strong game played on the edge set of a graph G there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of G (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a clique K[subscript k], a perfect matching, a Hamilton cycle, etc.). In this paper we consider strong games played on the edge set of a random graph G ∼ G(n, p) on n vertices. We prove that G ∼ G(n, p) is typically such that Red can win the perfect matching game played on E(G), provided that p ∈ (0, 1) is a fixed constant. 2017-06-19T15:06:48Z 2017-06-19T15:06:48Z 2017-02 2015-07 Article http://purl.org/eprint/type/JournalArticle 1077-8926 1097-1440 http://hdl.handle.net/1721.1/110013 Ferber, Asaf and Pascal Pfister. "Strong games played on random graphs." The Electronic Journal of Combinatorics 24.1 (2017): n. pag. en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p35/pdf Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf European Mathematical Information Service (EMIS) Electronic Journal of Combinatorics |
| spellingShingle | Ferber, Asaf Pfister, Pascal Strong games played on random graphs |
| title | Strong games played on random graphs |
| title_full | Strong games played on random graphs |
| title_fullStr | Strong games played on random graphs |
| title_full_unstemmed | Strong games played on random graphs |
| title_short | Strong games played on random graphs |
| title_sort | strong games played on random graphs |
| url | http://hdl.handle.net/1721.1/110013 |
| work_keys_str_mv | AT ferberasaf stronggamesplayedonrandomgraphs AT pfisterpascal stronggamesplayedonrandomgraphs |