Timeline for What is the complexity of the winning condition in infinite Hex? In particular, is infinite Hex a Borel game?
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 10, 2023 at 21:15 | answer | added | Ilkka Törmä | timeline score: 9 | |
| Jul 6, 2023 at 23:37 | comment | added | Christopher King | Does considering different rational rotations of the board help for the infinite tree thing? This can be achieved by embedding it into a large grid. | |
| Jul 6, 2023 at 18:39 | answer | added | Christopher King | timeline score: 5 | |
| Dec 2, 2022 at 7:32 | comment | added | Ville Salo | FWIW I think this is in the top 3 of questions this year, and the downvote and close vote baffle me. | |
| Dec 1, 2022 at 14:20 | comment | added | Joel David Hamkins | If someone could help me understand the close/down votes, I'd be grateful. Is the question unsuitable in some way? | |
| Dec 1, 2022 at 2:03 | review | Close votes | |||
| Dec 1, 2022 at 18:39 | |||||
| Nov 30, 2022 at 17:39 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
clarified some points with better explanation
|
| Nov 30, 2022 at 4:05 | comment | added | Joel David Hamkins | The way it works is that Red wins the finite rhombus boards, but with different chains depending on the center. No one chain fulfills the infinite winning condition. | |
| Nov 30, 2022 at 3:38 | comment | added | Joel David Hamkins | These are not equivalent, because of the Zen garden example in our paper. Red does not win, but wins on all sufficiently large rhombuses at any given center. (Perhaps one can play with the quantifiers here regarding the center/size.) | |
| Nov 30, 2022 at 3:26 | comment | added | Arno | Do you know whether "blue is winning on arbitrarily large finite subareas" is different from "red is not winning the full infinite game"? | |
| Nov 30, 2022 at 3:14 | comment | added | Joel David Hamkins | I am now leaning possibly even toward arithmetic, by thinking of the possible ways Blue can prevent a Red win... | |
| Nov 30, 2022 at 3:00 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 196 characters in body
|
| Nov 30, 2022 at 2:48 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 207 characters in body
|
| Nov 30, 2022 at 2:31 | comment | added | Noah Schweber | Ah, I see, it's much trickier than I thought. | |
| Nov 30, 2022 at 2:30 | comment | added | Joel David Hamkins | The difficulty with embedding the trees is that branching nodes will amount to an infinite line of some kind, with the option nodes coming off of it. But you cannot allow that the branching line itself is a winning path, and so it basically needs to be horizontal (or vertical) or infinitely often return to below a horizontal line. I don't see how to arrange that with all the branching nodes, which occur at successively higher levels of the tree. | |
| Nov 30, 2022 at 2:12 | comment | added | Joel David Hamkins | I've tried this, but you need infinitely branching trees, and there doesn't seem to be any way to do this easily, since there isn't enough room. This is the same obstacle that prevents us from embedding well founded trees into infinite chess. But if you see a way to embed the trees, such that branches through the trees correspond exactly to a win, then I would love to see it. This would clearly show that it is $\Sigma^1_1$ complete and hence not Borel. My vague impression is that the colorings of the tiles seem to exhibit a locally compact nature that prevents the tree embeddings from working. | |
| Nov 30, 2022 at 2:10 | comment | added | Noah Schweber | What if we just try to embed a tree $T\subseteq\omega^{<\omega}$ into the hex plane directly? This is a bit messy to do (in order to accommodate infinite branching, everything has to space out a lot) but I don't see a real obstacle to doing it. If this works, this gives $\Sigma^1_1$-completeness immediately. | |
| Nov 30, 2022 at 2:01 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 204 characters in body
|
| Nov 30, 2022 at 1:51 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 205 characters in body
|
| Nov 30, 2022 at 1:39 | history | asked | Joel David Hamkins | CC BY-SA 4.0 |