Return to Question

Clearly, the winning condition has complexity $\Sigma^1_1$ at worst, since Red wins if and only if there is a winning Red $\Z$-chain, which amounts to a second-order existential quantifier to get the $\Z$-chain, and to assert that a given $\Z$-chain is winning for Red involves only number quantifiers, since one needs only to say that it is connected, that it is entirely Red, and that it fulfills the infinite convergence property from lower left to upper right. On its face, therefore, infinite Hex is an analytic game, one whose winning condition has complexity $\Sigma^1_1$. But is the game truly $\Sigma^1_1$? I find it likely that the complexity bound can be improved.

Question 2. Is infinite Hex a Borel game? That is, is the set of winning Red plays a Borel set?

I conjecture that infinite Hex is a Borel game. To prove this, it would suffice to find an existential reason for Red not to have won any given position. For example, perhaps Red fails to win if and only if there is a series of Blue-or-noncolored tiles forming larger and larger obstacles, which would prevent a Red win. For example, perhaps Blue has downward sloping lines connecting the positive y-axis to the positive x-axis for some choice of center, as in the trapezoidal figures of our paper, or perhaps Blue has stones infinitely far into quadrant I that are connected to stones in quadrants II and IV, for any choice of center. If there were always such an existential reason for Red to lose, this would show that the non-winning plays were also $\Sigma^1_1$, making the Red wins $\Delta^1_1$ and hence Borel. This seems to be a promising approach, but I don't yet grasp a full account of the details here.

Meanwhile, the centrality of the question is that ZFC proves that all Borel games are determined, and one might hope to use this, if the winning condition were Borel, to prove that either one of the players has a winning strategy in infinite Hex or both players have drawing strategies. In fact, we already know (the main initial result of our paper above) that both players have drawing strategies in infinite Hex, starting from an empty board. But we don't have this result yet for the infinite Hex games arising from arbitrary finite positions, even ones with a single extra stone, and we actually have no proof that such games are determined. But surely they are determined!

Clearly, the winning condition has complexity $\Sigma^1_1$ at worst, since Red wins if and only if there is a winning Red $\Z$-chain, which amounts to a second-order existential quantifier to get the $\Z$-chain, and to assert that a given $\Z$-chain is winning for Red involves only number quantifiers, since one needs only to say that it forms a connected chain, that it is entirely Red, and that it fulfills the infinite convergence property from lower left to upper right. On its face, therefore, infinite Hex is an analytic game, one whose winning condition has complexity $\Sigma^1_1$. But is the game truly $\Sigma^1_1$? I find it likely that the complexity bound can be improved.

Question 2. Is infinite Hex a Borel game? That is, is the set of (partial) colorings of the hex board that are winning for Red a Borel set?

I conjecture that infinite Hex is a Borel game. To prove this, it would suffice to find an existential characterization for Red NOT to have won a given position. For example, perhaps Red fails to win if and only if there is a series of Blue-or-noncolored tiles forming larger and larger obstacles, which would prevent a Red win. For example, perhaps Blue has downward sloping lines connecting the positive y-axis to the positive x-axis for some choice of center, as in the trapezoidal figures of our paper, or perhaps Blue has stones infinitely far into quadrant I that are connected to stones in quadrants II and IV, for any choice of center. (Note that the question whether any two Blue stones are connected is an arithmetic property, requiring the quantification only over finite sequences and not infinite sequences.) If there were always such an existential reason for Red to lose, this would show that the non-winning plays were also $\Sigma^1_1$, making the Red wins $\Delta^1_1$ and hence Borel. This seems to be a promising approach, but I don't yet grasp a full account of the details here.

Meanwhile, the centrality of the complexity question is that ZFC proves that all Borel games are determined, and one might hope to use this, if the winning condition were Borel, to prove that either one of the players has a winning strategy in infinite Hex or both players have drawing strategies. In fact, we already know (the main initial result of our paper above) that both players have drawing strategies in infinite Hex, starting from an empty board. But we don't have this result yet for the infinite Hex games arising from arbitrary finite positions, even ones with a single extra stone, and we actually have no proof that such games are determined. But surely they are determined!

If infinite Hex is indeed Borel, what is the Borel complexity? It doesn't seem to be arithmetic, but I don't know how to prove this.

Question 4. Is infinite Hex not arithmetic?

If infinite Hex is indeed Borel, what is the Borel complexity? It doesn't seem to be arithmetic, but perhaps a clever argument would show that it is. Perhaps one need only say that Red wins, just in case Blue has not placed stones exhibiting certain finitary connectivity properties with respect to choices of center origin.

Question 4. Is infinite Hex an arithmetic game?

My question is about the complexity of the winning condition.

I conjecture that infinite Hex is a Borel game. To prove this, it would suffice to find an existential reason for Red not to have won any given position. For example, perhaps Red fails to win if and only if there is a series of Blue-or-noncolored tiles forming larger and larger obstacles, downward sloping lines connecting the positive y-axis to the positive x-axis for some choice of center, as in the trapezoidal figures of our paper. If there were always such an existential reason for Red to lose, this would show that the non-winning plays were also $\Sigma^1_1$, making the Red wins $\Delta^1_1$ and hence Borel. This seems to be a promising approach, but I don't yet grasp a full account of the details here.

My question is about the complexity of the standard winning condition.

I conjecture that infinite Hex is a Borel game. To prove this, it would suffice to find an existential reason for Red not to have won any given position. For example, perhaps Red fails to win if and only if there is a series of Blue-or-noncolored tiles forming larger and larger obstacles, which would prevent a Red win. For example, perhaps Blue has downward sloping lines connecting the positive y-axis to the positive x-axis for some choice of center, as in the trapezoidal figures of our paper, or perhaps Blue has stones infinitely far into quadrant I that are connected to stones in quadrants II and IV, for any choice of center. If there were always such an existential reason for Red to lose, this would show that the non-winning plays were also $\Sigma^1_1$, making the Red wins $\Delta^1_1$ and hence Borel. This seems to be a promising approach, but I don't yet grasp a full account of the details here.