PaperlayerView exact revision on arXiv

Source-linked AI summary

Ramsey Obstructions to Disambiguation

Romain Bourneuf, Antonin Kiladjian, Stéphan Thomassé

arXiv:2609.16359v1cs.DMmath.CO

TL;DR

The paper asks whether filling unspecified entries can inevitably create complexity absent from a partial matrix, including under strong local restrictions. It uses Ramsey-theoretic constructions to show that every disambiguation can contain highly complex patterns, even when the partial object is simple.

  • Problem

    The paper asks whether additional restrictions on a partial matrix can guarantee a disambiguation of bounded VC-dimension, after prior examples showed complexity could increase upon filling unspecified entries.

    Source: §1 · pp. 1–2

  • Method

    For the geometric construction, the proof applies Pálvölgyi’s Dense Block theorem to obtain structured restrictions that retain the gap constraints.

    Source: Overview of the proofs · p. 7

  • Results

    The paper establishes obstructions across margin matrices, locally constant partial matrices, and partial graphs, including a Littlestone-dimension-1 class whose every disambiguation has infinite VC-dimension.

    Source: §1 · pp. 2, 4, 5

  • Takeaways & Limitations

    The results show that unspecified entries can be essential to low complexity: the learnability of a partial class need not be explained by any learnable class of total extensions.

    Source: §1 · p. 2

    The local matrix construction cannot additionally forbid a fixed constant matrix, since filling every unspecified entry with the opposite constant preserves its absence.

    Source: §1 · p. 5

Abstract

from arXiv · show

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<\pi/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 $\pi-\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\'alv\"olgyi's Dense Block theorem, while the combinatorial constructions rely on the girth Ramsey theorem of Reiher and R\"odl, a suitable strengthening of the induced Ramsey theorem.

1 Introduction

The introduction presents partial matrices with low VC-dimension whose disambiguations can have arbitrarily high VC-dimension, across geometric, locally restricted, and graph settings. It outlines Ramsey-theoretic proofs using geometric structure and girth-Ramsey constructions to force prescribed patterns under every disambiguation.

1 Introduction

  • The proofs use Ramsey theory to find structured submatrices and explicitly construct shattered sets, rather than forcing distinct rows and applying the Sauer–Shelah lemma [AHHM22, CHHH23].For the geometric argument, Pálvölgyi’s Dense Block theorem yields structure on a discrete torus, and even cycles transfer the conclusion to Hamming cubes.Source: §1 · pp. 2, 4
  • A partial matrix with rank 1 over F2 and no pure 2 × 2 submatrix can have disambiguations of rank at least ⌈log2 n⌉.Its n rows are distinguished pairwise by columns indexed by row pairs.Source: §1 · pp. 2–3
  • For every fixed 0 < ε < π/2 and k, every disambiguation of M_ε^d has VC-dimension at least k for all sufficiently large d.The partial matrices have VC-dimension bounded independently of d, and their family is disambiguation-universal.Source: §1 · p. 4
  • For every 0 < ε < 1/2 and k, every disambiguation of the Gap-Hamming matrix H_ε^N has VC-dimension at least k for all sufficiently large N.The standard embedding of the Hamming cube as normalized sign vectors transfers this result to the spherical theorem.Source: §1 · p. 4
  • For every k, a finite partial matrix can have only constant pure 2 × 2 submatrices and VC-dimension at most 1, while every disambiguation has VC-dimension at least k.The pure 2 × 2 condition is equivalent to requiring every pure submatrix with at least two rows and two columns to be constant.Source: §1 · pp. 4–5
  • There is a partial concept class of Littlestone dimension 1 whose restrictions to n domain points admit disambiguations of at most n + 1 concepts, yet every full-class disambiguation has infinite VC-dimension.The construction uses a countable disjoint union of the finite matrices from Theorem 3, leaving entries between blocks unspecified.Source: §1 · p. 5
  • For every k, a finite partial graph of VC-dimension at most 1 can have only homogeneous pure induced subgraphs on three vertices, while every disambiguation contains every k-vertex graph as an induced subgraph.Source: §1 · p. 5

Overview of the proofs

  • The proof overview proposes finding a near-spanning homothetic copy of a smaller cube on which a symmetric coloring is radial, so its gap constraints force a color change that yields a shattered set.Conjecture 6 asserts such radial copies; the overview explains that the homogeneous dual Ramsey conjecture implies Conjecture 6, which in turn implies the Gap-Hamming Disambiguation theorem.Source: Overview of the proofs · p. 6
  • Pálvölgyi’s Dense Block theorem [Pá26] yields two embeddings whose coloring depends on coordinatewise distances while approximately preserving normalized distances, enabling the Gap-Hamming Disambiguation proof.The argument uses a discrete torus, exploits distance-level changes to construct a shattered set, and transfers the result to a cube by embedding even cycles isometrically into Hamming cubes.Source: Overview of the proofs · p. 7
  • Unspecified entries form edges of a row–column bipartite graph; prescriptions on induced pattern copies yield large VC-dimension under uniform fillings, while every pure 2 × 2 submatrix is constant in the construction.Source: Overview of the proofs · pp. 7–8
  • For graphs, the same strategy gives a partial graph whose two uniform disambiguations each contain every graph of the prescribed order, while every pure triple is homogeneous and no pair is shattered.The local forest structure supports these restrictions.Source: Overview of the proofs · p. 8

Preliminaries

  • A column set is shattered when rows realize every binary labeling of it, and the matrix VC-dimension is the supremum of finite shattered-set sizes.The preliminaries also define [n] and the integer interval notation Ja, bK.Source: Preliminaries · p. 8

AI statement

  • The authors state that ChatGPT assisted with proof discovery, literature searches, and manuscript organization and exposition, while they take full responsibility for the results, proofs, references, and final text.Source: AI statement · p. 8

2 Metric obstructions to disambiguation

This section establishes VC-dimension lower bounds for metric gap colorings, using Pálvölgyi’s Dense Block theorem and embeddings to transfer results among tori, hypercubes, and spheres. The statements cover spherical disambiguations and torus gap colorings uniformly over side lengths.

2.1 Shattering from distance profiles

  • For every ε and q, sufficiently large even-side discrete tori force VC-dimension at least q in every ε-gap distance-profile-canonical coloring.A maximal 0-colored distance profile leaves at least q coordinates whose independent color changes encode arbitrary subsets.Source: §2.1 · pp. 9–10

2.2 Canonicalization on a torus

  • Pálvölgyi’s Dense Block theorem [P´a26] produces an ε/2-gap distance-profile-canonical restriction of any ε-gap torus coloring using separate row and column embeddings.The embeddings preserve the gap constraints while canonicalizing colors by coordinatewise distance profiles.Source: §2.2 · pp. 11–12

2.3 From tori to the hypercube

  • Combining canonicalization with distance-profile shattering shows that every ε-gap coloring of a sufficiently large discrete torus has VC-dimension at least q.Pullback preserves the shattered set’s size, so the bound for the canonical restriction also holds for the original coloring.Source: §2.3 · p. 13
  • Every disambiguation of H^N_ε has VC-dimension at least k for every 0 < ε < 1/2 and all sufficiently large N.The proof transfers the torus result using an isometric embedding of an even cycle into a hypercube.Source: §2.3 · p. 13
  • Every corresponding disambiguation of H_N^ε has VC-dimension at least k, by transferring an ε/2-gap coloring on (Z_R)^n through ψ.The map ψ scales distances by a and satisfies the diameter condition needed to apply Lemma 9; Theorem 13 and Lemma 10 transfer the VC-dimension bound.Source: §2.3 · p. 13

2.4 Spherical and toroidal consequences

  • For every 0 < ε < π/2 and k, every disambiguation of M_ε^d has VC-dimension at least k for all sufficiently large d.The theorem makes the family {M_ε^d : d ≥ 1} disambiguation-universal.Source: §2.4 · p. 14
  • The spherical bound follows by mapping the hypercube into the sphere so short and long cube distances meet the spherical ε thresholds, then transferring the gap-coloring dimension bound.The proof uses η = 1 − cos ε / 2 and Lemma 10 to pass the lower bound from the hypercube coloring to the spherical coloring.Source: §2.4 · p. 14
  • For every 0 < ε < 1/2 and q, all sufficiently high-dimensional ε-gap colorings of (Z_R)^N have VC-dimension at least q, uniformly for R ≥ 2.The hypercube embeds as a scaled isometric copy in each discrete torus, allowing the bound to transfer to every side length.Source: §2.4 · p. 14

3 Girth Ramsey and Disambiguations

This section uses the girth Ramsey theorem and localization in forests of copies to construct partial matrices and graphs with restrictive local patterns but high-complexity disambiguations, including partial graphs whose every disambiguation contains every k-vertex graph as an induced subgraph despite homogeneous pure induced subgraphs on three vertices and VC-dimension at most 1.

3.1 The girth-Ramsey theorem

  • The girth Ramsey theorem [RR23] supplies induced copies so every edge-coloring has a monochromatic copy, while every family of at most ℓ copies lies in a forest of copies.For bipartite patterns, the host and copies can also be chosen bipartite and side-respecting.Source: §3.1 · p. 15

3.2 Localization in forests of copies

  • Forests of copies yield a tree-decomposition of adhesion at most 2, in which copies intersect only along a vertex or edge and cliques and specified 4-cycles localize to one copy.This localization supports compatible prescriptions and checks of local restrictions.Source: §3.2 · p. 16

3.3 The matrix construction

  • For every k, a finite partial matrix has constant pure 2×2 submatrices and VC-dimension at most 1, yet every disambiguation has VC-dimension at least k.The construction arranges copies of a partial pattern so that every 0/1 coloring makes one copy uniform; either uniform filling has VC-dimension at least k.Source: §3.3 · pp. 18–19

3.4 The graph construction

  • For every k, a finite partial graph has VC-dimension at most 1 and only homogeneous pure induced triples, yet every disambiguation contains every k-vertex graph.The supplied theorem states this result; the construction begins by selecting a partial graph whose two uniform fillings each contain every k-vertex graph.Source: §3.4 · p. 19
  • Every disambiguation of G contains every k-vertex graph as an induced subgraph.A monochromatic member of F yields a copy of U(b) in the disambiguation, and U(b) contains all k-vertex graphs as induced subgraphs.Source: §3.4 · p. 20
  • Every pure induced subgraph of G on three vertices is homogeneous.Such a triple lies in a common Q ∈ F, where its induced graph is inherited from U, which has no vertex incident to both an edge and a non-edge.Source: §3.4 · p. 20
  • G has VC-dimension at most 1 because it has no shattered set of size 2.The contradiction argument uses four distinct common neighbors of two vertices and Lemma 17(c).Source: §3.4 · p. 20

A The radial Ramsey approach

The appendix gives a conditional route from the Near-Spanning Radial Ramsey Conjecture to Gap-Hamming Disambiguation, and derives the radial conjecture from Homogeneous Dual Ramsey. Symmetry, scaling, and near-spanning conditions are essential to the stated Ramsey guarantees.

A The radial Ramsey approach

  • The radial conjecture seeks a symmetric coloring’s near-spanning homothetic cube copy on which pair color depends only on distance.It requires 0 < ε < 1/2 and allows an ε-near-spanning copy of any prescribed dimension.Source: A The radial Ramsey approach · p. 23
  • Symmetry is necessary: coloring ordered pairs by a fixed vertex order gives opposite colors to reversed pairs, contradicting radiality.Radiality requires the two colors to agree.Source: A The radial Ramsey approach · p. 23
  • The Near-Spanning Radial Ramsey Conjecture implies the Gap-Hamming Disambiguation theorem.The appendix states this implication as Lemma 20.Source: A The radial Ramsey approach · p. 24
  • A homothetic cube copy encodes equal-sized active coordinate blocks, linking radial copies to Ramsey questions about merging partition parts.The appendix relates this representation to homogeneous dual Ramsey theory, which concerns partitions and coarsening.Source: A The radial Ramsey approach · p. 24
  • The Homogeneous Dual Ramsey Conjecture implies the Near-Spanning Radial Ramsey Conjecture, and therefore conditionally implies Gap-Hamming Disambiguation.The appendix presents this as Theorem 21 and Corollary 22.Source: A The radial Ramsey approach · p. 24
  • Both scaling and near-spanning allowance are necessary: parity excludes monochromatic isometric Q1 copies, while first-coordinate coloring excludes spanning Q1 copies.For pair colorings, even a near-spanning homothetic Q2 need not be monochromatic, motivating radiality instead.Source: A The radial Ramsey approach · p. 24

A.1 Near-Spanning Radial Ramsey implies Gap-Hamming Disambiguation

Assuming the Near-Spanning Radial Ramsey Conjecture, the appendix derives large VC-dimension for every Gap-Hamming coloring. The proof symmetrizes the coloring with controlled VC-dimension, then uses radiality and a change between distance levels to shatter a large set.

A.1 Near-Spanning Radial Ramsey implies Gap-Hamming Disambiguation

  • Symmetrizing an ε-gap coloring of VC-dimension at most q yields one of VC-dimension at most B(q) = 2 log2(6)(q + 2q+1 −1).The construction sets ec(x,y) = c(x,y) ∨ c(y,x), preserving the gap constraints.Source: §A.1 · p. 25
  • The Near-Spanning Radial Ramsey Conjecture implies that every ε-gap coloring of a sufficiently large cube has VC-dimension at least q.The proof first establishes the result for symmetric colorings, then transfers it to arbitrary colorings using a VC-dimension bound for symmetrization.Source: §A.1 · p. 25
  • For a symmetric ε-gap coloring c and its c-radial ε/2-near-spanning homothetic copy ϕ: Qm→Qn, the induced f satisfies f(i)=0 for every i≤s+1 and f(m−s+1)=1.Source: §A.1 · pp. 25–26
  • For every subset J of [s], a witness at distances τ and τ−2 from the unit vectors realizes exactly the pattern indexed by J, shattering s points.The construction chooses τ as the first distance level colored 1 and uses witnesses xJ to separate membership from nonmembership.Source: §A.1 · p. 26

A.2 From homothetic copies to balanced partitions

The appendix characterizes homothetic maps between Hamming cubes by equal-sized coordinate blocks. This representation connects such copies to balanced partitions and motivates the dual Ramsey approach.

A.2 From homothetic copies to balanced partitions

  • Every homothetic map from Qm to Qn has equal-sized, pairwise disjoint active coordinate blocks and fixed remaining coordinates.For x in Qm, coordinates in block Ui take the corresponding bit xi, possibly flipped by a fixed vector z; coordinates outside the active blocks remain fixed.Source: §A.2 · p. 26
  • The converse also holds: this block representation defines a homothetic map whose distances are scaled by the common block size.The appendix says the classification is included for context; the subsequent construction uses balanced block maps.Source: §A.2 · pp. 26–27

A.3 Yet another conjecture

The section generalizes homogeneous dual Ramsey theory to prescribed rational profiles. Its conjecture seeks a refinement that makes each coloring constant across all coarsenings of a chosen partition.

A.3 Yet another conjecture

  • A profile is a finite vector of positive rational numbers whose entries sum to 1.Its number of entries is denoted p(α).Source: §A.3 · p. 27
  • Partitions are represented by rigid surjections, and refinement corresponds to composing with a rigid surjection that merges parts.A copy of one profile in another specifies how to merge parts while preserving the prescribed profile sizes.Source: §A.3 · p. 27
  • The Multi-Profile Dual Ramsey Conjecture asks for a β-partition whose coarsenings have a constant color separately for each profile α(i).The color may differ between profile indices; the homogeneous dual Ramsey conjecture is the single-profile special case.Source: §A.3 · p. 27

A.4 Homogeneous Dual Ramsey implies Multi-Profile Dual Ramsey

The section proves that Homogeneous Dual Ramsey implies the Multi-Profile Dual Ramsey Conjecture, using profile amalgamation and an induction over the number of profiles. Since the multi-profile statement generalizes the homogeneous one, the conjectures are equivalent.

A.4 Homogeneous Dual Ramsey implies Multi-Profile Dual Ramsey

  • The Amalgamation Lemma constructs a common refinement of two profiles while making their given copies of a coarser profile agree.This supplies the iterative step for arranging each α-copy in the distinguished β-copy as a canonical coarsening of an HD-copy.Source: §A.4 · pp. 28, 30
  • The single-profile result follows by encoding each coloring of α-partitions as a coloring of HD-partitions and applying Homogeneous Dual Ramsey.The constructed β-partition has all its α-coarsenings the same color.Source: §A.4 · pp. 29–30
  • Profile Dual Ramsey implies the multi-profile statement by induction, first homogenizing one coloring and then homogenizing the remaining colorings.The proof transfers the remaining colorings to a smaller set of coordinates before applying the induction hypothesis.Source: §A.4 · pp. 30–31
  • The Homogeneous Dual Ramsey Conjecture implies the Multi-Profile Dual Ramsey Conjecture.The proof first derives the single-profile Profile Dual Ramsey result, then extends it by induction over the profiles.Source: §A.4 · pp. 29–31
  • The two conjectures are equivalent because Multi-Profile Dual Ramsey generalizes Homogeneous Dual Ramsey.The reverse implication is the immediate specialization to one profile.Source: §A.4 · p. 31

A.5 Multi-Profile Dual Ramsey implies Near-Spanning Radial Ramsey

Assuming Multi-Profile Dual Ramsey, the section obtains near-spanning radial homothetic copies in hypercubes for every symmetric coloring. It encodes Hamming distances through coordinate-partition profiles and then adjusts the near-spanning parameter by repeating coordinates.

A.5 Multi-Profile Dual Ramsey implies Near-Spanning Radial Ramsey

  • Assuming Multi-Profile Dual Ramsey, every symmetric coloring of Q^n × Q^n admits a c-radial 1/(m+1)-near-spanning homothetic copy of Q^m for sufficiently large n.The statement is Lemma 34.Source: §A.5 · p. 31
  • The proof encodes pairs of cube vertices by coordinate partitions whose profiles record their Hamming distance, so color constancy across profiles yields radiality.Each input bit is represented by a pair of equal blocks, and the chosen block determines its value.Source: §A.5 · pp. 31–32
  • For every ε > 0 and m, Multi-Profile Dual Ramsey implies the Near-Spanning Radial Ramsey Conjecture for symmetric colorings.Choose t so that 1/(tm+1) ≤ ε, apply Lemma 34 to Q^(mt), and repeat each coordinate t times to obtain the required copy.Source: §A.5 · p. 32
Loading 2609.16359v1…