pith. sign in

arxiv: 2606.12880 · v1 · pith:NKHWEUWBnew · submitted 2026-06-11 · 🧮 math.CO

Monochromatic k in a row

Kuo-Han Ku This is my paper

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

classification 🧮 math.CO
keywords k-in-a-rowavoiding configurationsextremal densityinteger gridhypercubecombinatorial gamecollinear points
0
0 comments X

The pith

The maximum density of k-in-a-row avoiding sets on the integer grid equals exactly 1 minus 2 over k when 3 does not divide k.

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

The paper examines extremal densities of configurations that contain no k points in arithmetic progression on two families of boards. On the infinite grid it proves the upper bound D(k,Z²) equals 1-2/k precisely when k is not a multiple of 3 and determines the exact values of both the maximum and minimum densities when k equals 3. On the finite hypercube it supplies matching bounds for the maximum density to order k to the minus 2 and identifies the exact minimum density. These quantities measure the largest or smallest fraction of positions that can be occupied without forming a monochromatic line of length k, a constraint that appears when the usual maker-breaker game is altered so that any claimed point contributes to the final alignment.

Core claim

We establish that D(k,ℤ²)=1−2/k whenever 3∤k, and both D(3,ℤ²) and d(3,ℤ²) are determined exactly; we also bound the minimum density d(k,ℤ²) up to a gap of (8+o(1))k^{-1}. For hypercubes [k]^d we derive asymptotic bounds on D(k,[k]^d) up to order k^{-2} and obtain the exact value of d(k,[k]^d).

What carries the argument

The extremal densities D(k, board) and d(k, board) of sets whose claimed positions contain no k-in-a-row.

If this is right

  • When 3 does not divide k the largest possible density of a k-in-a-row avoiding set on Z² is exactly 1-2/k.
  • Both the maximum and minimum densities are known exactly when k equals 3.
  • The gap between upper and lower bounds for d(k,Z²) is at most (8+o(1))/k.
  • On the hypercube [k]^d the minimum density d(k,[k]^d) is known exactly and the maximum density is pinned down to within an additive error of order k^{-2}.

Where Pith is reading between the lines

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

  • The exact minimum density on hypercubes may suggest a canonical construction that could be lifted to the infinite grid for small k.
  • The contrast drawn with the classical no-(k+1)-in-line problem indicates that the choice of constraint (all claimed points versus only one color) changes which bounds are attainable.
  • The counting arguments used on Z² might extend directly to other periodic lattices such as the triangular grid.

Load-bearing premise

The variant game produces a well-defined notion of k-in-a-row avoiding configurations whose extremal densities can be bounded by standard combinatorial constructions and counting arguments on Z^2 and [k]^d.

What would settle it

An explicit subset of Z² whose density exceeds 1-2/k yet contains no k collinear points, for any k not divisible by 3, would falsify the claimed upper bound on D.

Figures

Figures reproduced from arXiv: 2606.12880 by Kuo-Han Ku.

Figure 1
Figure 1. Figure 1: F5 Note that, when k ě 4, such pattern contains no near k-line and adding any remaining point in the ground set [k + 2]2 creates a near k-line within the ground set. For ℓ = n(k + 2) P (k + 2)N, let S be the subset built by tiling Fk over [ℓ] 2 . In particular, we define S := ď vP((k+2)[0,n´1])2 Fk + v. It is clear that S contains no near k-lines. Given a point x P [ℓ] 2 zS, let vx P ((k + 2)[0, n ´ 1])2 b… view at source ↗
Figure 2
Figure 2. Figure 2: F 1 5 ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 5
Figure 5. Figure 5: Rare structure ‹: possible positions for y (Positions in gray are outside [ℓ] 2 .) For ℓ P 5N, [ℓ] 2 can be partitioned into horizontal 5-lines. Let L be a such partition, then we can lower bound the maximum density by D(3, [ℓ] 2 ) ě |Sℓ | ℓ 2 = 1 ℓ 2 ÿ LPL |Sℓ X L| = 1 ℓ 2 ˆ ℓ 2 5 ˆ 1 = 1 5 . Let ℓ go to infinity, we derive D(3, Z 2 ) ě 1 5 . We now upper bound the maximum density. Given a saturated confi… view at source ↗
Figure 6
Figure 6. Figure 6: displays S ‹ and several types of building blocks for k = 8 and d = 2. w ϕ(w)(B) = B X Et1,2u z ϕ(z)(B) = R1(B) X E2 x w z y [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: X5 and X6 For the minimum density, recall that d(k, [k] d ) = (1 ´ 2 k ) d . In fact, there is a family of configurations reaching minimum density, and this family includes the previous example [2, k ´ 1]d . For each i P [t k 2 u], define Wi := ([k]zti,(k + 1) ´ iu) d . Given a k-line L = v +[0, k ´1]d in [k] d , the two points, v + (i´1)d and v + (k ´i)d, are not contained in Wi . Hence Wi misses at least… view at source ↗
Figure 8
Figure 8. Figure 8: several configurations Thus, further analysis requires additional restrictions or assumptions on the players. s-Saturated Configurations We can extract the concept of saturated config￾uration and quantize it. Given a k-board B. For every s P [k], we define the s-configurations Ck,s(B) := tS Ď B : |LzS| ě s @ k-line Lu. Then we accordingly define the saturated s-configurations, Sk,s(B). Further, if B is fin… view at source ↗
read the original abstract

We study a variant of the $k$-in-a-row game in which players alternatively claim positions until a $k$-in-a-row is created among all claimed positions. This leads to the constraint near $k$-in-a-row avoiding on configurations and the associated problem of determining their extremal densities of such configurations. We investigate this problem on two types of boards: the grid $\mathbb{Z}^2$ and hypercubes $[k]^d$. For the grid $\mathbb{Z}^2$, we establish nearly tight bounds on the maximum density $D(k,\mathbb{Z}^2)$, showing that $D(k,\mathbb{Z}^2)=1-\frac{2}{k}$ whenever $3\nmid k$, and determine both $D(3,\mathbb{Z}^2)$ and $d(3,\mathbb{Z}^2)$ exactly. We also bound the minimum density $d(k,\mathbb{Z}^2)$ up to a gap of $(8+o(1))k^{-1}$. For hypercubes $[k]^d$, we derive asymptotic bounds on $D(k,[k]^d)$ up to order $k^{-2}$ and obtain the exact value of $d(k,[k]^d)$. Our results contrast with the classical no-$(k+1)$-in-line problem, a similar problem imposing different constraint, where the trivial upper bound is conjectured to be attainable.

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.

Referee Report

0 major / 3 minor

Summary. The manuscript examines extremal densities of k-in-a-row avoiding sets arising from a variant game on the integer grid ℤ² and on the discrete hypercubes [k]^d. It claims that the maximum density satisfies D(k,ℤ²)=1−2/k exactly whenever 3 does not divide k, determines both D(3,ℤ²) and d(3,ℤ²) exactly, bounds the minimum density d(k,ℤ²) within a gap of (8+o(1))k^{-1}, and obtains asymptotic bounds on D(k,[k]^d) to order k^{-2} together with the exact value of d(k,[k]^d). These are derived via periodic tilings for the upper bounds and explicit constructions for the matching lower bounds, contrasting with the classical no-(k+1)-in-line problem.

Significance. If the periodic counting arguments and constructions hold, the work supplies nearly tight, explicit densities for a natural avoidance problem in combinatorial extremal theory. The matching upper and lower bounds for all k not divisible by 3, the separate exact computation for k=3, and the parameter-free nature of the periodic averaging are concrete strengths that advance the quantitative understanding of line-avoiding configurations.

minor comments (3)
  1. [Introduction] §1 (Introduction): the precise definition of the allowed directions for k-in-a-row should be stated explicitly before the density statements, as the abstract leaves the line orientations implicit.
  2. [Abstract] The o(1) term in the gap for d(k,ℤ²) is stated without an explicit reference to the section deriving the 8/k coefficient; adding a forward pointer would improve readability.
  3. [Section 2] Notation for D versus d is introduced without a dedicated sentence contrasting maximum versus minimum density; a single clarifying sentence early in §2 would prevent reader confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the strengths of the periodic arguments and constructions, and recommendation of minor revision.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives D(k,ℤ²)=1-2/k (for 3∤k) via an explicit periodic tiling upper bound that counts forbidden k-tuples per cell and a matching (k,2)-periodic construction for the lower bound; the k=3 case is handled by separate explicit computation. These are standard self-contained combinatorial arguments on the grid and hypercube that do not reduce to fitted parameters, self-definitions, or load-bearing self-citations. The abstract and skeptic analysis confirm the results contrast with prior work without internal reduction to inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard combinatorial density arguments and the definition of the game variant; no free parameters, new entities, or ad-hoc axioms are visible in the abstract.

axioms (2)
  • standard math Asymptotic density is well-defined for subsets of ℤ² and [k]^d
    Required to define D(k,ℤ²), d(k,ℤ²), and the corresponding quantities on hypercubes.
  • standard math Standard double-counting and construction techniques apply to line-avoiding sets
    Invoked implicitly to obtain the stated upper and lower bounds.

pith-pipeline@v0.9.1-grok · 5771 in / 1404 out tokens · 32210 ms · 2026-06-27T06:43:53.006693+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 8 canonical work pages

  1. [1]

    SIAM Journal on Discrete Mathematics , volume=

    Incidence bounds for block designs , author=. SIAM Journal on Discrete Mathematics , volume=. 2016 , publisher=

    2016

  2. [2]

    SIAM Journal on Discrete Mathematics , volume=

    Finite field Kakeya and Nikodym sets in three dimensions , author=. SIAM Journal on Discrete Mathematics , volume=. 2018 , publisher=

    2018

  3. [3]

    Positional Games

    Hefetz, Dan and Krivelevich, Michael and Stojakovi \' c , Milo s and Szab \'o , Tibor. Positional Games. 2014. doi:10.1007/978-3-0348-0825-5_1

    work page doi:10.1007/978-3-0348-0825-5_1 2014

  4. [4]

    Sharp density bounds on the finite field

    Bukh, Boris and Chao, Ting-Wei , journal =. Sharp density bounds on the finite field. doi:10.19086/da.30707 , year =

    work page doi:10.19086/da.30707

  5. [5]

    arXiv preprint arXiv:2502.17655 , year=

    Volume estimates for unions of convex sets, and the Kakeya set conjecture in three dimensions , author=. arXiv preprint arXiv:2502.17655 , year=

    arXiv

  6. [6]

    arXiv preprint arXiv:0803.3525 , year=

    On the size of Nikodym sets in finite fields , author=. arXiv preprint arXiv:0803.3525 , year=

    Pith/arXiv arXiv

  7. [7]

    Combinatorial Games: Tic-Tac-Toe Theory , isbn =

    Beck, József , publisher =. Combinatorial Games: Tic-Tac-Toe Theory , isbn =. 2008 , pages =

    2008

  8. [9]

    Some advances in the no-three-in-line problem , journal =

    R.R Hall and T.H Jackson and A Sudbery and K Wild , abstract =. Some advances in the no-three-in-line problem , journal =. 1975 , issn =. doi:https://doi.org/10.1016/0097-3165(75)90043-6 , url =

    work page doi:10.1016/0097-3165(75)90043-6 1975

  9. [10]

    Update on the no-three-in-line problem , journal =

    David Brent Anderson , abstract =. Update on the no-three-in-line problem , journal =. 1979 , issn =. doi:https://doi.org/10.1016/0097-3165(79)90025-6 , url =

    work page doi:10.1016/0097-3165(79)90025-6 1979

  10. [11]

    Progress in the no-three-in-line-problem , journal =

    Achim Flammenkamp , abstract =. Progress in the no-three-in-line-problem , journal =. 1992 , issn =. doi:https://doi.org/10.1016/0097-3165(92)90012-J , url =

    work page doi:10.1016/0097-3165(92)90012-j 1992

  11. [12]

    Progress in the No-Three-in-Line Problem, II , journal =

    Achim Flammenkamp , keywords =. Progress in the No-Three-in-Line Problem, II , journal =. 1998 , issn =. doi:https://doi.org/10.1006/jcta.1997.2829 , url =

    work page doi:10.1006/jcta.1997.2829 1998

  12. [13]

    L.V. Allis. Searching for solutions in games and artificial intelligence. 1994. doi:10.26481/dis.19940923la

    work page doi:10.26481/dis.19940923la 1994

  13. [14]

    2025 , type =

    Kuo-Han Ku , title =. 2025 , type =. doi:10.6342/NTU202501210 , url =

    work page doi:10.6342/ntu202501210 2025

  14. [15]

    L.V. Allis. Searching for solutions in games and artificial intelligence . PhD thesis, Maastricht University, January 1994

    1994

  15. [16]

    Update on the no-three-in-line problem

    David Brent Anderson. Update on the no-three-in-line problem. Journal of Combinatorial Theory, Series A , 27(3):365--366, 1979

    1979

  16. [17]

    Combinatorial Games: Tic-Tac-Toe Theory , pages 159--161

    József Beck. Combinatorial Games: Tic-Tac-Toe Theory , pages 159--161. Cambridge University Press, 01 2008

    2008

  17. [18]

    Progress in the no-three-in-line-problem

    Achim Flammenkamp. Progress in the no-three-in-line-problem. Journal of Combinatorial Theory, Series A , 60(2):305--311, 1992

    1992

  18. [19]

    Progress in the no-three-in-line problem, ii

    Achim Flammenkamp. Progress in the no-three-in-line problem, ii. Journal of Combinatorial Theory, Series A , 81(1):108--113, 1998

    1998

  19. [20]

    No- (k+ 1) -in-line problem for large constant k

    Alexandr Grebennikov and Matthew Kwan. No- (k+ 1) -in-line problem for large constant k . arXiv preprint arXiv:2510.17743 , 2025

    arXiv 2025

  20. [21]

    Some advances in the no-three-in-line problem

    R.R Hall, T.H Jackson, A Sudbery, and K Wild. Some advances in the no-three-in-line problem. Journal of Combinatorial Theory, Series A , 18(3):336--341, 1975

    1975

  21. [22]

    Monochromatic k in a row

    Kuo-Han Ku. Monochromatic k in a row. Master's thesis, National Taiwan University, 2025

    2025