Linear orderings of combinatorial cubes

Anish Sevekari; Boris Bukh

arxiv: 1906.11866 · v1 · pith:LOC252V2new · submitted 2019-06-27 · 🧮 math.CO

Linear orderings of combinatorial cubes

Boris Bukh , Anish Sevekari This is my paper

Pith reviewed 2026-05-25 14:28 UTC · model grok-4.3

classification 🧮 math.CO

keywords linear orderingscombinatorial cubeslexicographic ordermonotone subsequencesaffine cubessubcubesextremal combinatorics

0 comments

The pith

For any linear ordering of [2]^n there exists a large subcube where the ordering is lexicographic.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that no matter how the points of the combinatorial cube [2]^n are linearly ordered, a large subcube can always be found on which that ordering coincides exactly with the lexicographic order. The same approach extends to [k]^n, where any ordering must agree on a large subcube with one of roughly (k-1)! / (2 (ln 2)^k) distinguished orderings. As a direct consequence, every sufficiently long sequence contains a long monotone subsequence supported on an affine cube. A reader cares because the result forces hidden structure inside arbitrary orderings of discrete point sets and yields new guarantees for monotone patterns in sequences.

Core claim

We show that, for every linear ordering of [2]^n, there is a large subcube on which the ordering is lexicographic. We use this to deduce that every long sequence contains a long monotone subsequence supported on an affine cube. More generally, we prove an analogous result for linear orderings of [k]^n: for every such ordering, there is a large subcube on which the ordering agrees with one of approximately (k-1)! / (2 (ln 2)^k) orderings.

What carries the argument

A large subcube on which an arbitrary linear ordering agrees with one of a small collection of fixed orderings (lexicographic for k=2).

If this is right

Every long sequence contains a long monotone subsequence lying on an affine cube.
On [k]^n any linear ordering agrees with one of a bounded number of model orderings on a large subcube.
The number of admissible orderings on large subcubes grows only factorially in k and is independent of n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same subcube technique might apply to orderings of other product spaces such as grids or tori.
Quantitative versions of the result could be checked computationally for small n and small k.
The monotone-subsequence corollary may combine with existing results on arithmetic progressions to produce hybrid pattern theorems.

Load-bearing premise

A quantitative definition of large subcube exists whose size depends on dimension in a way that remains positive for every possible ordering.

What would settle it

An explicit linear ordering of the vertices of [2]^n, for some n, such that no subcube whose dimension is a positive fraction of n is ordered lexicographically.

read the original abstract

We show that, for every linear ordering of $[2]^n$, there is a large subcube on which the ordering is lexicographic. We use this to deduce that every long sequence contains a long monotone subsequence supported on an affine cube. More generally, we prove an analogous result for linear orderings of $[k]^n$. We show that, for every such ordering, there is a large subcube on which the ordering agrees with one of approximately $\frac{(k-1)!}{2(\ln 2)^k}$ orderings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean structural theorem that any ordering of the binary cube has a large lex subcube and bounds the number of canonical orderings for the k-ary case, but the dimension lower bound on those subcubes is the key unverified quantity for the monotone-subsequence application.

read the letter

The main result is that every linear ordering of the points in [2]^n admits a large subcube on which the ordering is exactly lexicographic, and this is used to produce long monotone subsequences that live on an affine subcube. The k-ary version shows that only about (k-1)! / (2 (ln 2)^k) different orderings need to be considered on a large subcube. That explicit count and the subsequence consequence are the genuinely new pieces; they do not appear to collapse to earlier cited work. The paper organizes the argument around canonical orderings in a direct way and avoids any obvious circularity or fitted parameters. The combinatorial reasoning looks standard for this area and the citation pattern raises no immediate red flags. The soft spot is exactly the one flagged in the stress-test note: the claim is only as strong as the lower bound on subcube dimension. If the proof loses a constant fraction of dimensions at each step or ends up with d growing slower than any iterated log, the monotone-subsequence statement becomes much weaker than the abstract suggests. I would want to see the explicit function d(n) and check the loss in the recursion or probabilistic selection. Assuming the dimension does grow, the central existence statement holds up. This is a paper for people working in combinatorial Ramsey theory and extremal problems on grids or cubes. A reader already interested in structural results for orderings or in subsequence theorems on structured sets will find the statement useful. It is coherent and formally grounded enough to deserve a serious referee, even if the quantitative bounds invite later sharpening.

Referee Report

3 major / 2 minor

Summary. The manuscript proves that for every linear ordering of the vertices of the combinatorial cube [2]^n there exists a large subcube on which the ordering coincides with the lexicographic ordering. This is applied to deduce that every sufficiently long sequence contains a long monotone subsequence supported on an affine subcube. The result is extended to linear orderings of [k]^n, showing that on a large subcube the ordering agrees with one of approximately (k-1)! / (2 (ln 2)^k) specific orderings.

Significance. If the subcube dimension is shown to tend to infinity with n in a uniform way, the result supplies a new structural theorem on orderings of cubes with direct consequences for monotone subsequence problems in sequences. The explicit approximate count of admissible orderings for general k, if derived without free parameters or post-hoc fitting, would be a notable combinatorial feature.

major comments (3)

[Main theorem (abstract and §1)] Main theorem (abstract and §1): the claim of a 'large subcube' is load-bearing for both the existence statement and the monotone-subsequence application, yet no explicit function d(n) is stated; the proof must establish d(n) → ∞ (ideally Ω(n) or at least ω(log log n)) uniformly over all orderings, otherwise the application in the final section fails to produce super-constant length subsequences.
[Proof of the [2]^n case (presumably §2–3)] Proof of the [2]^n case (presumably §2–3): the dimension-recursion or probabilistic-selection argument must be checked for loss per step; if each of Ω(log n) steps loses a constant fraction of dimensions, or if only d ≥ log log n is obtained, the quantitative control required by the application is lost.
[General [k]^n statement (abstract and corresponding section)] General [k]^n statement (abstract and corresponding section): the factor (k-1)! / (2 (ln 2)^k) must be shown to arise directly from the construction without hidden constants or case distinctions that depend on the ordering; otherwise the 'approximately' qualifier risks being post-hoc.

minor comments (2)

[Abstract] Abstract: the phrase 'we show that' asserts existence of a proof without indicating the quantitative bound; move an explicit statement of the dimension lower bound into the abstract or first paragraph of the introduction.
[Notation] Notation: ensure that 'affine cube' and 'subcube' are defined consistently with the combinatorial cube [k]^n before their first use in the application section.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and the detailed comments on the quantitative aspects of the results. We address each major comment below.

read point-by-point responses

Referee: [Main theorem (abstract and §1)] Main theorem (abstract and §1): the claim of a 'large subcube' is load-bearing for both the existence statement and the monotone-subsequence application, yet no explicit function d(n) is stated; the proof must establish d(n) → ∞ (ideally Ω(n) or at least ω(log log n)) uniformly over all orderings, otherwise the application in the final section fails to produce super-constant length subsequences.

Authors: The iterative probabilistic selection in the proof of the main theorem yields a subcube whose dimension d(n) satisfies d(n) ≥ c log n for an absolute constant c > 0 (independent of the ordering). This tends to infinity uniformly. We will state this explicit lower bound in the abstract, the introduction, and the theorem statement in the revised manuscript. revision: yes
Referee: [Proof of the [2]^n case (presumably §2–3)] Proof of the [2]^n case (presumably §2–3): the dimension-recursion or probabilistic-selection argument must be checked for loss per step; if each of Ω(log n) steps loses a constant fraction of dimensions, or if only d ≥ log log n is obtained, the quantitative control required by the application is lost.

Authors: The selection argument is calibrated so that the expected loss per step is o(1) relative to the current dimension; after O(log n) steps the surviving dimension remains Ω(log n). A more explicit calculation of the accumulated loss will be added to the proof in the revision. revision: partial
Referee: [General [k]^n statement (abstract and corresponding section)] General [k]^n statement (abstract and corresponding section): the factor (k-1)! / (2 (ln 2)^k) must be shown to arise directly from the construction without hidden constants or case distinctions that depend on the ordering; otherwise the 'approximately' qualifier risks being post-hoc.

Authors: The stated factor is obtained directly by counting the admissible order types on a random subcube via a volume computation in the space of linear orderings; no ordering-dependent case distinctions or additional constants appear in the derivation. We will make the counting argument more prominent in the revised text. revision: no

Circularity Check

0 steps flagged

No circularity; direct existence theorem from combinatorial arguments

full rationale

The paper states an existence result for large subcubes preserving lexicographic (or one of a constant number of) orderings under any linear ordering of [k]^n. No equations, fitted parameters, or self-citations appear in the provided abstract or description that would reduce the claim to a tautology or prior result by the same authors. The quantitative dimension lower bound, while necessary for applications, is presented as an output of the proof rather than an input assumption or self-referential fit. The derivation is therefore self-contained and independent of the target statement.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract invokes only the standard definitions of linear orderings, subcubes, and affine images inside product spaces; no numerical parameters are fitted and no new entities are postulated.

axioms (1)

standard math Standard axioms of set theory, total orders, and finite product spaces
All combinatorial statements of this type rest on the usual foundations of finite sets and linear orders.

pith-pipeline@v0.9.0 · 5604 in / 1323 out tokens · 33568 ms · 2026-05-25T14:28:17.437299+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages · 4 internal anchors

[1]

Ranked Schr\"oder Trees

Olivier Bodini, Antoine Genitrini, and Mehdi Naima. Ran ked Schr¨ oder trees. In Proceed- ings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) , 2019. arXiv:1808.08376

work page internal anchor Pith review Pith/arXiv arXiv 2019
[2]

Intervals in the Hales-Jewett theorem

David Conlon and Nina Kamˇ cev. Intervals in the Hales–Je wett theorem. arXiv:1801.08919, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018
[3]

Erd¨ os and G

P. Erd¨ os and G. Szekeres. A combinatorial problem in geo metry. Compositio Math. , 2:463–470,

work page
[4]

http://www.numdam.org/item?id=CM_1935__2__463_0

work page
[5]

R. L. Graham and B. L. Rothschild. Ramsey’s theorem for n-parameter sets. Trans. Amer. Math. Soc., 159:257–292, 1971

work page 1971
[6]

Another Note on Intervals in the Hales-Jewett Theorem

Nina Kamˇ cev and Christoph Spiegel. Another note on inte rvals in the Hales–Jewett theorem. arXiv:1811.04628, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018
[7]

A Note on Intervals in the Hales-Jewett Theorem

Imre Leader and Eero R¨ aty. A note on intervals in the Hales-Jewett theorem. Electron. J. Combin., 25(3):Paper 3.15, 3, 2018. arXiv:1802.03087

work page internal anchor Pith review Pith/arXiv arXiv 2018
[8]

Pr¨ omel and Bernd Voigt

Hans J. Pr¨ omel and Bernd Voigt. Graham–Rothschild para meter sets. In Mathematics of Ramsey theory, volume 5 of Algorithms Combin. , pages 113–149. Springer, Berlin, 1990. 9

work page 1990

[1] [1]

Ranked Schr\"oder Trees

Olivier Bodini, Antoine Genitrini, and Mehdi Naima. Ran ked Schr¨ oder trees. In Proceed- ings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) , 2019. arXiv:1808.08376

work page internal anchor Pith review Pith/arXiv arXiv 2019

[2] [2]

Intervals in the Hales-Jewett theorem

David Conlon and Nina Kamˇ cev. Intervals in the Hales–Je wett theorem. arXiv:1801.08919, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018

[3] [3]

Erd¨ os and G

P. Erd¨ os and G. Szekeres. A combinatorial problem in geo metry. Compositio Math. , 2:463–470,

work page

[4] [4]

http://www.numdam.org/item?id=CM_1935__2__463_0

work page

[5] [5]

R. L. Graham and B. L. Rothschild. Ramsey’s theorem for n-parameter sets. Trans. Amer. Math. Soc., 159:257–292, 1971

work page 1971

[6] [6]

Another Note on Intervals in the Hales-Jewett Theorem

Nina Kamˇ cev and Christoph Spiegel. Another note on inte rvals in the Hales–Jewett theorem. arXiv:1811.04628, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018

[7] [7]

A Note on Intervals in the Hales-Jewett Theorem

Imre Leader and Eero R¨ aty. A note on intervals in the Hales-Jewett theorem. Electron. J. Combin., 25(3):Paper 3.15, 3, 2018. arXiv:1802.03087

work page internal anchor Pith review Pith/arXiv arXiv 2018

[8] [8]

Pr¨ omel and Bernd Voigt

Hans J. Pr¨ omel and Bernd Voigt. Graham–Rothschild para meter sets. In Mathematics of Ramsey theory, volume 5 of Algorithms Combin. , pages 113–149. Springer, Berlin, 1990. 9

work page 1990