A complete solution to the biased Alon-Krivelevich-Spencer-Szabó criterion problem for the discrepancy game

Abstract

Let \(H=(V,\mathcal E)\) be a finite hypergraph. For positive integers \(p\) and \(q\), the \((p:q)\)-biased discrepancy game on \(H\) is played in complete rounds. In each round, Balancer first claims \(p\) previously unclaimed vertices, and then Unbalancer claims \(q\) previously unclaimed vertices. Let \(B\) and \(U\) be the final sets of vertices claimed by Balancer and Unbalancer, respectively. For an edge \(e\in\mathcal E\), define $D_e = q|B\cap e|-p|U\cap e| = (p+q)|B\cap e|-p|e|$. Thus \(D_e\) measures the deviation of Balancer's share of \(e\) from the density \(p/(p+q)\). In 2005, Alon, Krivelevich, Spencer and Szabó proved a Chernoff-type potential criterion for the unbiased alternating discrepancy game, corresponding to the case \(p=q=1\), and asked for a biased analogue for general $p,q$. In this paper, we prove a complete biased analogue in the complete-round formulation. More precisely, for every finite hypergraph \(H=(V,\mathcal E)\) and every fixed bias \((p:q)\), we give an explicit exponential condition under which Balancer has a strategy forcing $-L_e^- \le D_e \le L_e^+$ for every $e\in\mathcal E$, where \(L_e^+\) and \(L_e^-\) are prescribed edge-dependent target values.