47 problems

Let $C$ be a fixed graph containing three non-isolated vertices, and define its 2-density by … There are constants $c_1,c_2>0$ such that, for sufficiently large $n$, Maker wins the…

In a Maker–Breaker game and its corresponding Waiter–Client game, Maker and Waiter are the respective players seeking to claim a winning set. Beck's conjecture. Whenever Maker wins…

Let $G$ be the evolving random graph process, and write $\tau(\mathcal E)$ for the hitting time at which event $\mathcal E$ first occurs. Let ${\cal M}$ be the perfect matching gam…

Let ${\cal H}$ be the set of Hamiltonian cycles in $K_n$. For a family of winning sets ${\cal F}$, let $b_{\cal F}^p$ denote the smallest bias for which Breaker wins the random gam…

Let $C$ be a fixed graph. In the Maker–Breaker $C$-game on the edges of the complete graph $K_n$, Maker claims one edge per round and Breaker claims up to $q$ edges per round; Make…

Fallow-cell conjecture. Fallow cells are the only cells where both players ever want to play; moreover, the unique taut positions guaranteed by Theorem are the fallow positions wit…

Let ${\cal G}_{\mathrm{rhom}}$ denote the full rhombus game, and let $\text{SC}_2({\cal G},s)$ be the score achieved when Maker is restricted to a pairing strategy in an $s$-of-$k$…

Let $C_n$ be the cycle on $n$ vertices. For an $s$-of-$k$ game on a hypergraph ${\cal G}$, let $\text{SC}({\cal G},s)$ denote the optimal Maker score and let…

Let $G$ be a random graph, and let $\gamma_{MB}(G,b)$ and $s_{MB}(G,b)$ denote the two Maker–Breaker domination game parameters. For a Binomial random graph $G_{n,p}$ with constant…

Let $t(n,\mathcal{C})$ denote the threshold bias of the monotone $b$-biased Oriented-cycle game, in which OMaker aims to create a directed cycle and OBreaker aims to prevent one. T…

Let $t^+(n,\mathcal{C})$ denote the threshold bias of the strict $b$-biased Oriented-cycle game, where OMaker aims to create a directed cycle and OBreaker aims to prevent one. Boll…

Bounded-move conjecture. For every graph $H$, there is a constant $C_H$, depending only on $H$, such that

Beck's conjecture. For sufficiently large $n$ and every integer $t\geq 3$, there is a constant $c_t$, depending only on $t$, such that

Consider impartial Tak played on an $n\times n$ board, with the first player seeking a winning strategy. Odd-board first-player conjecture. If $n>5$ is odd, then the first player h…

Let $L(n)$ denote the quantity measuring the size of a minimal snake diagram. Quadratic lower-bound conjecture. For all $n$, … for some constants $a$ and $b$. This conjecture asser…

Let $n\geq 6$. Write $M_n$ for the value given by Proposition, and let $x$ satisfy … A penult is a position on an $n\times n$ board with the stated token count from which the relev…

Beck–Csernenszky–Mándity–Pluhár conjecture. If Maker wins the Maker-Breaker game on $H$ while going second, then Waiter wins the Waiter-Client game on $H$.

Let $K_n$ be the complete graph on $n$ vertices. In the $(1:1)$ Client–Waiter game, Waiter offers two board elements at each round and Client claims one; Client's claimed edges for…

Let $K_n$ be the complete graph on $n$ vertices. A graph is tree-universal at degree bound $D$ if it contains a copy of every tree $T$ with $n$ vertices and maximum degree…

Let $K_n$ be the complete graph on $n$ vertices. A graph is tree-universal at degree bound $D$ if it contains a copy of every tree $T$ with $n$ vertices and maximum degree…

A biased Maker–Breaker game is played by Maker and Breaker claiming elements of a board according to fixed rules; in a random-player version, the players act randomly, while in a p…

Maker's arborescence cost conjecture. W.h.p. over the random choice of $C$, Maker can construct a spanning arborescence $T$ satisfying

Maximum-score conjecture. The first player's score satisfies

Odd-cycle conjecture. For every odd integer $n\ge5$,

Let $H$ be a graph with $e(H)\ge 1$, and let $m(H)$ denote its maximum density over nonempty subgraphs, namely … Consider the $b$-Waiter–Client game on the edges of $K_n$, where Wa…