Positional games · 2014-econ-8

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

For each integer $k\ge 2$, let $D(k)$ be the minimum possible maximum vertex degree of a finite $k$-uniform hypergraph $\mathcal H$ on which Maker has a winning strategy in the following game: Maker and Breaker alternately claim one previously unclaimed vertex, Maker moves first, and Maker wins if he claims every vertex of some hyperedge of $\mathcal H$. Determine whether there exists a constant $\varepsilon>0$ such that $D(k)>(1+\varepsilon)^k$ for every integer $k\ge 2$.

Source reference: Heidi Gebauer, Tibor Szabó, and Gábor Tardos, “The Local Lemma Is Asymptotically Tight for SAT,” Journal of the ACM 63(5), Article 43 (2016), 43:1–43:32, Problem 7.1, doi:10.1145/2975386, arXiv:1006.0744.

Question 2

For each integer $k\ge 2$, let $D(k)$ be the minimum possible maximum vertex degree of a finite $k$-uniform hypergraph $\mathcal H$ on which Maker has a winning strategy in the following game: Maker and Breaker alternately claim one previously unclaimed vertex, Maker moves first, and Maker wins if he claims every vertex of some hyperedge of $\mathcal H$. Determine whether

$$D(k)=\left\lfloor\frac{k}{2}\right\rfloor+1$$

for every integer $k\ge 2$.

Source reference: Heidi Gebauer, Tibor Szabó, and Gábor Tardos, “The Local Lemma Is Asymptotically Tight for SAT,” Journal of the ACM 63(5), Article 43 (2016), 43:1–43:32, Problem 7.4, doi:10.1145/2975386, arXiv:1006.0744.

Question 3

For each integer $k\ge 2$, let $D(k)$ be the minimum possible maximum vertex degree of a finite $k$-uniform hypergraph on which Maker has a winning strategy when Maker and Breaker alternately claim one previously unclaimed vertex, Maker moves first, and Maker wins by claiming every vertex of a hyperedge. Let $D_{\mathrm{pair}}(k)$ be the analogous minimum under the additional requirement that Maker use a pairing strategy: Maker first claims a designated vertex $x_0$, the hypergraph has a fixed family of pairwise disjoint two-element vertex sets not containing $x_0$, and whenever Breaker claims one member of such a pair while its other member is unclaimed, Maker claims the other member on the next move. Prove that, for all sufficiently large $k$,

$$D(k)<D_{\mathrm{pair}}(k).$$

Source reference: Heidi Gebauer, Tibor Szabó, and Gábor Tardos, “The Local Lemma Is Asymptotically Tight for SAT,” Journal of the ACM 63(5), Article 43 (2016), 43:1–43:32, Problem 7.5, doi:10.1145/2975386, arXiv:1006.0744.