{"id":"arxiv/2609.16359","url":"https://arxiv.org/abs/2609.16359","tags":["cs.DM","math.CO"],"score":0,"title":"Ramsey Obstructions to Disambiguation","domain":"cs.DM","source":"arxiv","authors":["Romain Bourneuf","Antonin Kiladjian","Stéphan Thomassé"],"reviews":0,"subject":"cs.DM","summary":"A partial matrix has entries in $\\{0,1,\\star\\}$, and a disambiguation replaces each $\\star$ by $0$ or $1$. We construct partial matrices whose fully specified submatrices satisfy strong restrictions, yet every disambiguation contains every binary matrix of a prescribed size. Our first result answers a question of Alon, Hanneke, Holzman and Moran on the disambiguation of linear classifiers with margin. For $0<\\varepsilon<π/2$, let $M_\\varepsilon^d$ be the partial matrix indexed by points of the unit sphere $\\mathbb S^d$, with entry $0$ for pairs at spherical distance at most $\\varepsilon$,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}