Partial matrices with simple parts force complex patterns everywhere
Ramsey Obstructions to Disambiguation
Discrete Mathematics
Summary
This paper looks at partial grids filled with 0s, 1s, and uncertain entries marked as stars. The authors show that even if every small, fully decided part of the grid follows very simple rules, any way you replace the stars with 0s or 1s ends up containing every possible pattern of a certain size. They solve an open problem about classifying points with some margin and build grids with very limited complexity but unavoidably rich overall patterns. These findings connect to ideas in math about coloring and unavoidable patterns in large structures.
What this means in practice
- •For machine learning engineers: Avoid oversimplifying models with low VC-dimension that may still allow extremely complex data patterns when uncertain or ambiguous entries are resolved.
- •For graph algorithm designers: Understand limitations when attempting to simplify partial or incomplete graphs without losing critical induced subgraph structures across all completions.
A theory result. No direct application yet.
Authors
Romain Bourneuf, Antonin Kiladjian, Stéphan Thomassé
Abstract
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$, $1$ for pairs at distance at least $π-\varepsilon$, and $\star$ otherwise. Although these matrices have VC-dimension bounded independently of $d$, we prove that every disambiguation contains every binary $k\times k$ matrix once $d$ is sufficiently large. This also yields a partial concept class of Littlestone dimension $1$ with no disambiguation of finite VC-dimension. We also construct, for every $k$, a finite partial matrix whose fully specified $2\times2$ submatrices are all constant, while every disambiguation contains every binary $k\times k$ matrix. A symmetric analogue holds for partial graphs: for every $k$, there exists a partial graph of VC-dimension at most $1$ whose fully specified induced subgraphs are all cliques or stable sets, yet every disambiguation contains every $k$-vertex graph as an induced subgraph. A disambiguation can be viewed as a $2$-coloring of the unspecified entries, making Ramsey theory a natural framework for forcing prescribed patterns. Our proofs draw on two recent Ramsey theorems: the geometric argument uses Pálvölgyi's Dense Block theorem, while the combinatorial constructions rely on the girth Ramsey theorem of Reiher and Rödl, a suitable strengthening of the induced Ramsey theorem.