Search

We investigate games played between Maker and Breaker on an infinite complete graph whose vertices are coloured with colours from a given set, each colour appearing infinitely often. The players alternately claim edges, Maker's aim being to claim all edges of a sufficiently colourful infinite complete subgraph and Breaker's aim being to prevent this. We show that if there are only finitely many colours, then Maker can obtain a complete subgraph in which all colours appear infinitely often, but that Breaker can prevent this if there are infinitely many colours. Even when there are infinitely many colours, we show that Maker can obtain a complete subgraph in which infinitely many of the colours each appear infinitely often.

AbstractWe investigate Maker–Breaker games on graphs of size $\aleph _1$ in which Maker’s goal is to build a copy of the host graph. We establish a firm dependence of the outcome of the game on the axiomatic framework. Relating to this, we prove that there is a winning strategy for Maker in the $K_{\omega ,\omega _1}$ -game under ZFC+MA+ $\neg $ CH and a winning strategy for Breaker under ZFC+CH. We prove a similar result for the $K_{\omega _1}$ -game. Here, Maker has a winning strategy under ZF+DC+AD, while Breaker has one under ZFC+CH again.

Abstract We study programs that perform I/O and finite or countable nondeterministic choice, up to finite trace equivalence. For well-founded programs, we characterize which strategies (sets of traces) are definable, and axiomatize trace equivalence by means of commutativity between I/O and nondeterminism. This gives the set of strategies as an initial algebra for a polynomial endofunctor on semilattices. The strategies corresponding to non-well-founded programs constitute a final coalgebra for this functor. [ABSTRACT FROM AUTHOR]

AbstractWe prove that for a finitely generated infinite nilpotent group Gwith structure (G, ·, …), the connected component G*0of a sufficiently saturated extension G* of Gexists and equalsWe construct an expansion of Z by a predicate (Z, +, P) such that the type-connected component is strictly smaller than Z*0. We generalize this to finitely generated virtually solvable groups. As a corollary of our construction we obtain an optimality result for the van der Waerden theorem for finite partitions of groups.

AbstractWe introduce a precise framework for transferring strategies from simpler to more complex games, and use it to construct strategies in certain finite and infinite combinations of games. In particular, we give a finitary characterization of finite hypergraphs Xsuch that the first player can win the positional game on infinitely many copies of X. This resolves a conjecture of Leader.

We introduce a precise framework for transferring strategies from simpler to more complex games, and use it to construct strategies in certain finite and infinite combinations of games. In particular, we give a finitary characterization of finite hypergraphs Xsuch that the first player can win the positional game on infinitely many copies of X. This resolves a conjecture of Leader.

It is generally known that infinite symmetric groups have few nontrivial normal subgroups (typically only the subgroups of bounded support) and none of small index. (We will explain later exactly what we mean by small). However the standard analysis relies heavily on the axiom of choice. By dint of a lot of combinatorics we have been able to dispense—largely—with the axiom of choice. Largely, but not entirely: our result is that if Xis an infinite set with |X| = |X × X| then Symm(X) has no nontrivial normal subgroups of small index. Some condition like this is needed because of the work of Sam Tarzi who showed [4] that, for any finite group G, there is a model of ZF without AC in which there is a set Xwith Symm(X)/FSymm(X) isomorphic to G.The proof proceeds in two stages. We consider a particularly useful class of permutations, which we call the class of flexiblepermutations. A permutation of Xis flexible if it fixes at least |X|-many points. First we show that every normal subgroup of Symm(X) (of small index) must contain every flexible permutation. This will be theorem 4. Then we show (theorem 7) that the flexible permutations generate Symm(X).