On a clique-building game of Erdős
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918483187466240 |
|---|---|
| author | Malekshahian, Alexandru Spiro, Sam |
| author_facet | Malekshahian, Alexandru Spiro, Sam |
| contents | The following game was introduced in a list of open problems from 1983 attributed to Erdős: two players take turns claiming edges of a $K_n$ until all edges are exhausted. Player 1 wins the game if the largest clique that they claim at the end is strictly larger than the largest clique of their opponent; otherwise, Player 2 wins the game. Erdős conjectured that Player 2 always wins this game for $n\geq 3$. We make the first known progress on this problem, proving that this holds for at least $3/4$ of all such $n$. We also address a biased version of this game, as well as the corresponding degree-building game, both of which were originally proposed by Erdős as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18304 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On a clique-building game of Erdős Malekshahian, Alexandru Spiro, Sam Combinatorics The following game was introduced in a list of open problems from 1983 attributed to Erdős: two players take turns claiming edges of a $K_n$ until all edges are exhausted. Player 1 wins the game if the largest clique that they claim at the end is strictly larger than the largest clique of their opponent; otherwise, Player 2 wins the game. Erdős conjectured that Player 2 always wins this game for $n\geq 3$. We make the first known progress on this problem, proving that this holds for at least $3/4$ of all such $n$. We also address a biased version of this game, as well as the corresponding degree-building game, both of which were originally proposed by Erdős as well. |
| title | On a clique-building game of Erdős |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.18304 |