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

Gang Yang; Meiqin Wei; Yaping Mao

arxiv: 2606.13309 · v1 · pith:5JAAVCSXnew · submitted 2026-06-11 · 🧮 math.CO

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

Yaping Mao , Meiqin Wei , Gang Yang This is my paper

Pith reviewed 2026-06-27 06:25 UTC · model grok-4.3

classification 🧮 math.CO

keywords discrepancy gamebiased positional gamehypergraphBalancer strategyexponential criteriondeviation boundChernoff-type boundcombinatorial game

0 comments

The pith

For any finite hypergraph and bias (p:q), an explicit exponential condition lets Balancer force every edge deviation D_e inside prescribed bounds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper supplies a full biased extension of the 2005 Alon-Krivelevich-Spencer-Szabó criterion. It states a concrete exponential condition on the edges that guarantees Balancer a strategy to keep the deviation D_e between two chosen target values for each edge separately. The condition works for every finite hypergraph, every positive integers p and q, and fully non-uniform targets that may change from edge to edge. A reader would care because the result turns an existence question into a checkable criterion for who controls balance in a vertex-claiming game.

Core claim

For every finite hypergraph H=(V,E) and every fixed bias (p:q), an explicit exponential condition on the hypergraph ensures that Balancer has a strategy forcing -L_e^- ≤ D_e ≤ L_e^+ for every edge e, where D_e = q|B ∩ e| - p|U ∩ e| equals (p+q)|B ∩ e| - p|e| and the targets L_e^+ and L_e^- may be chosen independently for each edge. The condition is fully non-uniform: edge sizes, targets, and the exponential parameters can all vary with e.

What carries the argument

The explicit non-uniform exponential condition that bounds a potential involving terms exponential in the deviation scaled by the targets, allowing Balancer to maintain control over all D_e simultaneously.

If this is right

Balancer possesses an explicit strategy to keep all deviations inside the chosen bounds whenever the exponential condition holds.
The same criterion recovers the original unbiased result as the special case p = q = 1.
Targets and parameters can differ arbitrarily across edges without breaking the guarantee.
The result applies to every finite hypergraph without any uniformity requirement on edge sizes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The complete-round restriction means the criterion does not automatically cover games that end with a partial round.
The non-uniform form suggests the condition could be checked or optimized separately on different parts of a large hypergraph.
The potential-function approach used here may extend to other biased positional games that track linear deviations.

Load-bearing premise

The game consists only of complete rounds in which Balancer always claims exactly p vertices before Unbalancer claims exactly q vertices.

What would settle it

A concrete finite hypergraph, specific p and q, and explicit L_e^+ and L_e^- values satisfying the exponential condition, together with a play in which Unbalancer forces at least one D_e outside its interval.

read the original 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\'o 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. The criterion is fully non-uniform: the edge size $|e|$, the upper target $L_e^+$, the lower target $L_e^-$, and the exponential parameters in the condition may all vary with $e$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper supplies the biased non-uniform exponential criterion for the (p:q) discrepancy game that the 2005 AKSS work explicitly left open.

read the letter

This paper supplies the biased non-uniform exponential criterion for the (p:q) discrepancy game that the 2005 AKSS work explicitly left open. They state an explicit condition on the hypergraph under which Balancer can force the deviation D_e = q|B ∩ e| - p|U ∩ e| to stay between prescribed per-edge bounds -L_e^- and L_e^+ for every edge, and the condition is allowed to depend on edge size, the two targets, and the bias ratio.

The extension looks like a direct lift of the original potential-function argument, adjusted for the fixed bias and made non-uniform across edges. That is the concrete advance: the 2005 paper asked for exactly this generalization, and prior work did not contain a version that handles arbitrary (p:q) and edge-dependent L values at once.

The main boundary is the complete-round restriction. The game is defined so every round has exactly p Balancer claims followed by exactly q Unbalancer claims; an incomplete final round would change the deviation measure and could invalidate the stated bounds. The authors scope the claim to this formulation, so it is not an internal contradiction, but it does limit applicability to the version they define.

Within that scope the claim is consistent with the unbiased case and carries no obvious circularity or invented parameters. The abstract alone does not let me check the inductive step or potential construction in detail, but nothing in the stated result contradicts the 2005 reference.

This is for people who work on discrepancy games or positional games on hypergraphs. Anyone who needs the biased criterion will want the result once the proof is verified. It deserves a serious referee because it settles a specific open question with an explicit, checkable condition.

Referee Report

0 major / 2 minor

Summary. The manuscript claims a complete solution to the biased analogue of the 2005 Alon-Krivelevich-Spencer-Szabó criterion problem. For any finite hypergraph H=(V,ℰ) and fixed bias (p:q), it supplies an explicit exponential condition (non-uniform across edges) under which Balancer has a strategy in the complete-round (p:q)-discrepancy game to force -L_e^- ≤ D_e ≤ L_e^+ for every edge e, where D_e = q|B∩e| - p|U∩e| and the targets L_e^+, L_e^- may depend on e.

Significance. If the potential-function argument and inductive strategy hold, the result is a substantial advance: it resolves the open biased extension posed by AKSS, supplies the first fully non-uniform criterion that permits edge-dependent sizes, targets, and exponential parameters, and extends the unbiased Chernoff-type potential method to arbitrary fixed biases while preserving the complete-round formulation.

minor comments (2)

[Abstract] The abstract and introduction should explicitly state the precise form of the exponential condition (e.g., the product or sum over edges) rather than describing it only qualitatively as 'explicit exponential'.
[Abstract] Notation for the deviation D_e is introduced twice in the abstract; a single consolidated definition would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the contribution, and recommendation to accept. We are pleased that the work is recognized as resolving the biased extension of the AKSS problem with a fully non-uniform criterion.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper extends the 2005 Alon et al. unbiased criterion (different authors) to the biased (p:q) complete-round case via an explicit exponential potential condition on D_e. No self-citations appear in the load-bearing steps, no parameters are fitted then renamed as predictions, and no ansatz or uniqueness claim reduces to prior work by Mao/Wei/Yang. The derivation is scoped to the stated game rules and supplies an independent non-uniform criterion, making the result self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard finite-set combinatorics and the potential-function technique introduced in 2005; no numerical parameters are fitted and no new entities are postulated.

axioms (2)

domain assumption Every hypergraph under consideration is finite.
Explicitly stated in the abstract as the setting for the criterion.
domain assumption The exponential potential method from the 2005 unbiased case extends to the biased complete-round setting.
The abstract presents the new criterion as a direct analogue without additional combinatorial obstacles.

pith-pipeline@v0.9.1-grok · 5881 in / 1457 out tokens · 29242 ms · 2026-06-27T06:25:32.902201+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references

[1]

N. Alon, M. Krivelevich, J. Spencer and T. Szabó, Discrepancy games,Electronic J. Combin. 12 (2005), Research Paper 51

2005
[2]

Beck, Van der Waerden and Ramsey type games,Combinatorica1 (1981), 103–116

J. Beck, Van der Waerden and Ramsey type games,Combinatorica1 (1981), 103–116

1981
[3]

Beck,Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008

J. Beck,Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008

2008
[4]

Chazelle,The Discrepancy Method: Randomness and Complexity, Cambridge University Press, Cambridge, 2000

B. Chazelle,The Discrepancy Method: Randomness and Complexity, Cambridge University Press, Cambridge, 2000

2000
[5]

Erdős and J

P. Erdős and J. L. Selfridge, On a combinatorial game,J. Combin. Theory, Ser. A14 (1973), 298–301

1973
[6]

Frieze, M

A. Frieze, M. Krivelevich, O. Pikhurko and T. Szabó, The game of JumbleG,Combin. Prob. Comput.14 (2005), 783–793

2005
[7]

A. W. Hales and R. I. Jewett, Regularity and positional games,Trans. Amer. Math. Soc.106 (1963), 222–229

1963
[8]

Hefetz, M

D. Hefetz, M. Krivelevich, M. Stojaković and T. Szabó,Positional Games, Oberwolfach Seminars, Vol. 44, Birkhäuser/Springer, Basel, 2014

2014
[9]

Hefetz, M

D. Hefetz, M. Krivelevich and T. Szabó, Bart–Moe games, JumbleG and discrepancy,European J. Combin.28 (2007), 1131–1143. 19

2007
[10]

Lu, A matching game,Discrete Math.94 (1991), 199–207

X. Lu, A matching game,Discrete Math.94 (1991), 199–207

1991
[11]

Matoušek,Geometric Discrepancy: An Illustrated Guide, Springer, Berlin, 1999

J. Matoušek,Geometric Discrepancy: An Illustrated Guide, Springer, Berlin, 1999

1999
[12]

Spencer, Six standard deviations suffice,Trans

J. Spencer, Six standard deviations suffice,Trans. Amer. Math. Soc.289 (1985), 679–706. 20

1985

[1] [1]

N. Alon, M. Krivelevich, J. Spencer and T. Szabó, Discrepancy games,Electronic J. Combin. 12 (2005), Research Paper 51

2005

[2] [2]

Beck, Van der Waerden and Ramsey type games,Combinatorica1 (1981), 103–116

J. Beck, Van der Waerden and Ramsey type games,Combinatorica1 (1981), 103–116

1981

[3] [3]

Beck,Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008

J. Beck,Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008

2008

[4] [4]

Chazelle,The Discrepancy Method: Randomness and Complexity, Cambridge University Press, Cambridge, 2000

B. Chazelle,The Discrepancy Method: Randomness and Complexity, Cambridge University Press, Cambridge, 2000

2000

[5] [5]

Erdős and J

P. Erdős and J. L. Selfridge, On a combinatorial game,J. Combin. Theory, Ser. A14 (1973), 298–301

1973

[6] [6]

Frieze, M

A. Frieze, M. Krivelevich, O. Pikhurko and T. Szabó, The game of JumbleG,Combin. Prob. Comput.14 (2005), 783–793

2005

[7] [7]

A. W. Hales and R. I. Jewett, Regularity and positional games,Trans. Amer. Math. Soc.106 (1963), 222–229

1963

[8] [8]

Hefetz, M

D. Hefetz, M. Krivelevich, M. Stojaković and T. Szabó,Positional Games, Oberwolfach Seminars, Vol. 44, Birkhäuser/Springer, Basel, 2014

2014

[9] [9]

Hefetz, M

D. Hefetz, M. Krivelevich and T. Szabó, Bart–Moe games, JumbleG and discrepancy,European J. Combin.28 (2007), 1131–1143. 19

2007

[10] [10]

Lu, A matching game,Discrete Math.94 (1991), 199–207

X. Lu, A matching game,Discrete Math.94 (1991), 199–207

1991

[11] [11]

Matoušek,Geometric Discrepancy: An Illustrated Guide, Springer, Berlin, 1999

J. Matoušek,Geometric Discrepancy: An Illustrated Guide, Springer, Berlin, 1999

1999

[12] [12]

Spencer, Six standard deviations suffice,Trans

J. Spencer, Six standard deviations suffice,Trans. Amer. Math. Soc.289 (1985), 679–706. 20

1985