Linear orderings of combinatorial cubes

MaRDI QIDQ6321178zbMATH OpenFDO

Authors Boris Bukh, Anish Sevekari

Publication date 27 June 2019

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(ln2{)}^k$ orderings.

This page was built for publication: Linear orderings of combinatorial cubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6321178)