bibkey: caro2025oddindependencegrids authors: Yair Caro; Mirko Petruševski; Riste Škrekovski; Zsolt Tuza year: 2025 title: “The odd independence number of graphs, II: Finite and infinite grids and chessboard graphs” doi: null url: https://arxiv.org/abs/2510.01897v1 claim: “Studies odd independent sets (independent sets S such that every vertex outside S has no neighbour or an odd number of neighbours in S) in grids and chessboard graphs, proves the density bounds 3/8 ≤ ρ_od ≤ 5/13 for the infinite square grid, and asks in Problem 29 whether every independent set of size (3/8 + ε_n)n² in P_n □ P_n, ε_n → 0, contains all four neighbours of some vertex.” strata_touched:

• D5/S3/Combinatorics/OddIndependence/OddGrid license: citation-only triage: anchor

Caro, Petruševski, Škrekovski and Tuza, odd independence in grids

A set S of vertices is odd independent when it is independent and every vertex outside S has either no neighbour or an odd number of neighbours in S (Part I, arXiv:2509.20763). For the square grid the paper constructs odd independent sets of density 3/8 in which every vertex has 0, 1 or 3 neighbours in the set, proves the upper density bound 5/13, and asks in Problem 29 (Section 6.1) whether there is a sequence ε_n → 0 such that any (3/8 + ε_n)n² independent vertices of P_n □ P_n contain all four neighbours of some vertex. It notes that an affirmative answer would solve the odd independence problem of the infinite grid directly.

The module D5/S3/Combinatorics/OddIndependence/OddGrid answers Problem 29 affirmatively with ε_n = 4/n.

Verified locator

URL: https://arxiv.org/abs/2510.01897v1

• Locator: Section 6.1 (Concluding remarks, grids), Problem 29, and the remark preceding it on the density-3/8 construction. Version 1 posted 2 October 2025; no journal reference or DOI is listed.