k-Markov strategies in selection games

Steven Clontz | University of South Alabama | http://clontz.org

Spring Topology and Dynamics Conference 2017

at New Jersey City University

ω-length Games

Used to characterize properties in topology and infinite combinatorics

Two players (I and II) alternate choosing moves An and Bn during round n.

A winner is declared based on <A0,B0,A1,B1,...>.

I

II

A0

B0

A1

B1

A2

B2

...

...

Strategies for ω-length Games

Perfect-Information

A function that decides a player’s move based on all previous opponent moves.

σ: MM

σ(<A0,...,An>)

k-Tactical

A function that decides a player’s move based on last k-many of previous opponent moves.

σ: M≤kM

σ(<A0,...,Ak-1>)

k-Markov

A function that decides a player’s move based on last k-many of prev. opp. moves and round #.

σ: M≤k⨉ω→M

σ(<A0,...,Ak-1>,n)

Coding

A function that decides a player’s move based on player & opponent’s last move

σ: M≤2M

σ(<B,A>)

Why study such things?

Banach-Mazur Game BM(X) (1935)

Players E,N choose decreasing open neighborhoods. E wins if intersection is empty.

X is Baire iff E has no winning strategy.

N’s Markov strategies can be improved to tactical strategies.

N’s perfect-info strategies can be improved to coding strategies.

Question (Telgarsky): Can k be improved for k-tactical strategies? (False for k=2.)

Countable-Finite Games (1990s)

Player C chooses countable Cn; player F chooses finite Fn. F wins if ⋃Fn contains ⋃Cn.

Scheepers studied k-tactics for player F assuming that C must choose strict supersets. Any (k+3)-tactic may be improved to a 3-tactic.

Clontz studied several variations, in particular when F need only contain ⋂Cn. Any (k+2)-mark may be improved to a 2-mark.

Selection Games Gfin(A,B) (1990s)

Player A chooses An from A; player B chooses finite subset Bn. B wins if ⋃Bn belongs to B. Two common cases:

A=B=O the collection of open covers of X (Menger game). When X=L(κ), this is equivalent to Clontz variation of countable-finite game.

A=B=D the collection of dense subsets of X (selectively separable game).

Improving Selection Game Strategies

Theorem

Any (k+2)-Markov strategy for a selection game may be improved to a 2-Markov strategy.

Idea of Proof

We define a 2-Markov strategy τ by asking the known winning (k+2)-Markov strategy σ what to do if the opponent repeated each move k+1 times:

τ(<A,A’>,n)=⋃σ(<A,...,A,A’,...,A’>,kn+i)

Since σ knows how to defeat the attack <A0,...,A0,A1,...,A1,...>, τ also successfully defeats the arbitrary attack <A0,A1,...>. ◻

Observation: Knowing how your opponent changes moves between rounds is powerful.

Theorem

Assume ⋃A is countable and B is closed under supersets.

Any perfect information strategy for such a selection game may be improved to a Markov strategy.

Idea of Proof (1/2)

Our improved Markov strategy τ will not be able to recover perfect information. However, due to the countability of ⋃A, there are only countably many “interesting” moves (moves that produce distinct responses by the perfect information strategy σ) that player A can utilize during the game.

Our Markov strategy will deal with all of these. Suppose we have defined At for all Ø<t≤s<ω. Then there are only countably many members of the set
{σ(<As|1,As|2,...,As,A>):A∈A}⊆⋃A. Define As^<n> for n<ω such that
{σ(<As|1,As|2,...,As,A>):A∈A}={σ(<As|1,As|2,...,As,As^<n>>):n<ω}.

Idea of Proof (2/2)

Let b:ω→ω be a bijection. Our improved Markov strategy is defined by:

τ(<A>,n)=σ(<Ab(n)|1,Ab(n)|2,...,Ab(n),A>)

Importantly, note that τ(<A>,n)=σ(<Ab(n)|1,Ab(n)|2,...,Ab(n),Ab(n)^<m>>) for some m<ω, and thus τ(<A>,n)=σ(<Ab(k)|1,Ab(k)|2,...,Ab(k)>) for some k<ω.

To prove that τ is winning whenever σ is, from every attack <A’0,A’1,A’2,...> made by the opponent, one may extract a (possibly rearranged) subsequence equal to <Af|1,Af|2,Af|3,...> for some f:ω→ω.

Since σ defeats this attack, τ defeats <A’0,A’1,A’2,...>. ◻

Corollaries

Corollaries

Barman and Dow (2012): Gfin(D,D)

Every countable strategically SS space is Markov SS.

Question (Gruenhage): Are all strategically SS (or even 2-Markov selectively separable) spaces actually Markov SS?

Clontz (2015): Gfin(O,O)

Every second-countable strategically Menger space is Markov Menger.

Fact: L(ω1) is a 2-Markov Menger space that is not Markov Menger.

Further fact: Cp(L(ω1)) is a 2-Markov CDFT space that is not Markov CDFT. Its separable subspaces are 2-Markov SS. (Are they Markov SS?)

References

(Available at clontz.org)

  • A. V. Arkhangel′ ski˘ı. Hurewicz spaces, analytic sets and fan tightness of function spaces. Dokl. Akad. Nauk SSSR, 287(3):525–528, 1986.
  • Doyel Barman and Alan Dow. Selective separability and SS+. Topology Proc., 37:181–204, 2011.
  • Doyel Barman and Alan Dow. Proper forcing axiom and selective separability. Topology Appl., 159(3):806–813, 2012.
  • Steven Clontz. Applications of limited information strategies in Menger’s game (to appear).
  • Steven Clontz. Relating games of Menger, countable fan tightness, and selective separability (preprint).
  • Winfried Just, Arnold W. Miller, Marion Scheepers, and Paul J. Szeptycki. The combinatorics of open covers. II. Topology Appl., 73(3):241–266, 1996.
  • Robert A. McCoy and Ibula Ntantu. Topological properties of spaces of continuous functions, volume 1315 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1988.
  • Fritz Rothberger. Eine verschrfung der eigenschaft c. Fundamenta Mathematicae, 30(1):50–55, 1938.
  • Masami Sakai. Property C′ ′ and function spaces. Proc. Amer. Math. Soc., 104(3):917–919, 1988.
  • Marion Scheepers. Combinatorics of open covers. I. Ramsey theory. Topology Appl., 69(1):31– 62, 1996.

k-Markov strategies in selection games

Thanks! Questions?

Steven Clontz | University of South Alabama | http://clontz.org

Spring Topology and Dynamics Conference 2017

at New Jersey City University

k-Markov strategies in selection games - Google Slides