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
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 9, 2023 at 17:41 | comment | added | Christopher King | It's very weird because most attempts at constructing something that shows it is high complexity run into problems with geometry and space, but figuring out a low complexity description of those problems is, well, complicated XD. | |
| Jul 8, 2023 at 4:55 | comment | added | Joel David Hamkins | Looking forward to your solution! | |
| Jul 8, 2023 at 0:52 | comment | added | Ilkka Törmä | @JoelDavidHamkins I believe I can prove that my counterexample is in some sense the only one (all counterexamples must have a similar structure), and using this, that the complexity is at most $\Sigma^0_7$. It will take me some time to write the proof, though. | |
| Jul 7, 2023 at 13:02 | history | edited | Christopher King | CC BY-SA 4.0 |
added 61 characters in body
|
| Jul 7, 2023 at 11:24 | comment | added | Joel David Hamkins | I don't see how that idea can work. Once one adds another level of branching, it seems there just isn't room. | |
| Jul 7, 2023 at 9:54 | comment | added | Joel David Hamkins | Idea: let's try to use this kind of arrangement to code trees into the position, in such a way that there is a winning path if and only if the tree is ill-founded. This would show that the condition must be $\Sigma^1_1$ and not arithmetic or even Borel. | |
| Jul 7, 2023 at 8:02 | comment | added | Joel David Hamkins | I drew a picture of Ilkka's counterexample here: twitter.com/JDHamkins/status/1677225988034265090. Very nice! This is similar to our double comb, as Davide mentioned, but the extra wiggles make it a counterexample to the PyRulez proposal. | |
| Jul 7, 2023 at 7:44 | comment | added | Davide Leonessi | We did not include the candidate criterion mentioned by @JoelDavidHamkins because we weren't sure whether it was equivalent to the standard winning condition, in particular it seemed to be equivalent to a weaker "connected component" winning condition. In our paper we have a double-comb position which is an example of such a weaker win, and is similar to the position described by Ilkka Törmä. However, the statement of PyRulez seems not to consider that a win, by the choice of M? | |
| Jul 7, 2023 at 6:41 | comment | added | Ilkka Törmä | This counterexample does take up an entire quadrant, and I don't see a way of making it more compact, so maybe a couple quantifiers more could be sufficient... | |
| Jul 7, 2023 at 6:34 | comment | added | Ilkka Törmä | The direction ($\Longleftarrow$) is false, and I'll give a counterexample. Place a red tile $t$ somewhere, and place an infinite path of red tiles going directly to the north, starting from $t$. From this path, place an infinite number of finite branches $b$ directly to the east, so that for every choice of origin, at least one of them has an endpoint $s_b$ in quadrant I. From each $s_b$ continue the branch to the east and occasionally make a "detour" far north, east, and back south to the same horizontal line. The branches make these detours in unison to avoid collision. | |
| Jul 6, 2023 at 22:42 | comment | added | Joel David Hamkins | It was a comment in the source code, not in the pdf. We had commented it out, but I don't recall if it was because we had a counterexample or not. Perhaps my co-author can help me remember. | |
| Jul 6, 2023 at 22:39 | comment | added | Christopher King | @JoelDavidHamkins definitely an interesting and tricky problem! I didn't realize the paper discussed complexity; I'll have to check it out. | |
| Jul 6, 2023 at 21:51 | comment | added | Joel David Hamkins | Looking forward to any further progress you might make. Thanks for engaging with my question! It all seems a little trickier than one would expect, but having an arithmetic solution does not seem unreasonable to me. I have a feeling it will reduce to some cleverly chosen finitely branching tree and König's lemma. | |
| Jul 6, 2023 at 21:03 | history | edited | Christopher King | CC BY-SA 4.0 |
added 184 characters in body
|
| Jul 6, 2023 at 19:35 | comment | added | Joel David Hamkins | I looked at our paper again, and in the source file we proposed a candidate criterion: there is a Red stone such that for every choice of center it is connected to stones in the corresponding quadrants I and III, which are themselves connected to stones arbitrarily far out to infinity by finite paths that remain within the quadrant. I think this is equivalent to your characterization (so we did have the $\exists M\forall N$ idea). We had removed this comment, but I can't remember now whether that was because we had a counterexample or because we lacked proof. | |
| Jul 6, 2023 at 19:04 | comment | added | Joel David Hamkins | Let me add that in other contexts these kind of nonstandard number arguments can often be reduced to arguments via Konig's lemma. Namely, there is a tree of possible ways to connect t to various s's, and your condition via f amounts to a kind of finite-branching condition on this tree, and so one could hope to get the infinite path by Konig's lemma. But I don't quite see my way through the details using your idea. (Davide and I had looked at various approaches very like this, including nonstandard analysis, but we couldn't make it work. We didn't have your $\exists M\forall N$ idea though..) | |
| Jul 6, 2023 at 18:57 | comment | added | Joel David Hamkins | I'm a little confused about your argument. In the theorem statement, you say that s and the path from t to s can depend on the lines, but in the converse direction of the proof, you seem to assume that s works for all lines. I guess you want to use a single pair of hyperlines that are further out than any standard line, and then argue that this also works for standard lines. But the problem then would be that the f(l) you get might itself be nonstandard, and so the truncated path might not go to infinty on the standard board. | |
| Jul 6, 2023 at 18:49 | history | edited | Christopher King | CC BY-SA 4.0 |
added 3 characters in body
|
| Jul 6, 2023 at 18:39 | history | answered | Christopher King | CC BY-SA 4.0 |