How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
A long blockade has a wide support-invariant, support-uniform minor
Statement
For integers and , some integer has the following property. Every blockade of length at least and width has an equicardinal minor of length and width at least which is -support-uniform and -support-invariant.
Facts & Assumptions
Given: and as in the Statement. We may discard surplus blocks and take its length to be exactly .
Finite uniform Ramsey guarantees, for any finite coloring of the -subsets of a sufficiently large index set, a prescribed-size monochromatic subset (For positive there is an such that every -colouring of has a monochromatic -element set).
Proof
List the finitely many ordered trees on at most vertices. By repeated application of [L1], one tree at a time, choose large enough that every -block blockade has a -block sub-blockade whose trace is monochromatic for every tree on this list. This is a backward iteration of finitely many finite Ramsey numbers; when an order has fewer than blocks, its -vertex trace is empty.
For this , there are at most ordered-tree types on at most vertices: root each tree at its first ordered vertex; for size the parent map on the other ordered positions has at most possibilities, and . Each trace has at most supports. Thus the sum of all trace cardinalities is an integer in , where .
Start by trimming all blocks to width . Choose the largest integer for which an equicardinal contraction of the original -block blockade has width at least and . Such a exists because works. If were not -support-invariant, some contraction of it of width at least would remove a support from the trace of an ordered tree of size at most . Trim its blocks to equal size. Trimming can only remove further supports, so the new equicardinal contraction has width at least and cost at most . This contradicts maximality of . Hence is invariant and has width at least .
Apply the Ramsey choice of step 1.1 to : for each ordered tree of size , color every -subset of block indices by whether it belongs to its trace, and successively retain a monochromatic sub-blockade. Keep exactly blocks. Each trace is empty or contains every -subset, so this minor is -support-uniform.
Support-invariance survives taking a sub-blockade: extend any contraction of the sub-blockade to the discarded blocks unchanged; since all original blocks of have the same size, the extended contraction retains at least the same fraction of its width. A copy on retained indices survives in the extended contraction if and only if it survives in the restricted one. Thus the sub-blockade is also -support-invariant, equicardinal, and retains the width lower bound from step 2.1.
Depends on
Used by
Dependency tree · two levels
10 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Chudnovsky, Scott, Seymour and Spirkl, Pure pairs I, Lemmas 4.1–4.3 (standard reference, not scraped)