Linear orderings of combinatorial cubes
Boris Bukh Anish Sevekari


PRNU Based Source Camera Attribution for Image Sets Anonymized with Patch-Match Algorithm
    A. Emir Dirikaedfootnote*
    
=========================================================================================




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 (k-1)!/2(ln 2)^k orderings.




§ STATEMENT OF RESULTS



  
Monotone subsequences.
A classic result of Erdős and Szekeres <cit.> asserts that
every sufficiently long sequence (a_1,a_2,…) contains a subsequence
(a_i_1,…,a_i_m) of length m that is monotone. One may wonder
if one may strengthen this result by requiring that the set
of indices {i_1,…,i_m} is an arithmetically structured set.

Our first result is such a strengthening. Before stating it,
we recall that an affine -cube is a set of the form
{x_0+_1 x_1+…+_d x_d : _1,…,_d∈{0,1}}.
An affine -cube is proper if it contains 2^d distinct elements.


For every d, there exists m such that every sequence of m distinct real numbers
contains a monotone subsequence whose index set is a proper affine -cube. 


In this result one cannot replace affine cubes by arithmetic progressions.
More precisely, we observe the following.

There exist arbitrarily long sequences of distinct real numbers 
that contains no monotone subsequences whose index set is a 3-term
arithmetic progression.


We construct such sequences, which we dub 3-AP-free, 
inductively. We start with any sequence of length 1. For the induction step,
we note that if (a_1,…,a_m)
is any 3-AP-free sequence, and M>2max_i a_i, then 
(a_1,a_1+M,a_2,a_2+M,…,a_m,a_m+M) is also 3-AP-free.
Indeed, suppose {i,j,k} is a three-term arithmetic progression.
If the parities of i,j,k are the same, the sequence (a_i,a_j,a_k) is not monotone 
by induction. If the parities of i,j,k are different, then (a_i,a_j,a_k) is not monotone
by the choice of M.




  
Hales–Jewett-type result for [2]^n.
A common way to prove Ramsey results on the integers is to deduce
them from abstract statements about high-dimensional cubes. For example,
in this way one deduces van der Waerden's theorem from the Hales–Jewett
theorem, and Szemerédi's theorem from the density Hales–Jewett theorem.
Our proof of <ref> also follows this pattern: we deduce
<ref> from a Ramsey result about linear orderings of [2]^n.

As our most general result will apply not only to [2]^n, but 
to [k]^n for any k≥ 2, we introduce definitions at that
level of generality. 

We shall think of elements of [k]^n as words of length n over alphabet [k]. 
A -parameter word is a word p over alphabet [k]∪{*_1,…,*_d}
that contains each of *_1,…,*_d at least once. For any word w of length d 
(possibly over a different alphabet), we let p w be the word obtained from p by replacing each *_i
by w_i, for each i. For example, if p=21*_1*_2*_13 and w=31,
then p w=213133. 

If p is a -parameter word, then the set {p w : w∈ [k]^d}
can be naturally regarded as a copy of [k]^d inside [k]^n; we
thus call it a (combinatorial) -subcube. Two -parameter words that
differ in a permutation of {*_1,…,*_d} induce the same -subcube.
Call a -parameter word p canonical if the first occurrence
of *_1 precedes the first occurrence of *_2, which in turn precedes
the first occurrence of *_3, etc. 
Canonical words induce a canonical bijection between [k]^d and corresponding
-subcubes; we shall always use this bijection when identifying -subcubes
with [k]^d.

If p is a D-parameter word of length n and p' is a -parameter word of length
D, then p p' is a -parameter word of length n. Furthermore,
if both p and p' are canonical, then so is p p'. Hence,
if C_1⊇ C_2⊃…  is a nested chain of subcubes of [k]^n,
we may use the canonical bijection to regard C_i+1 as a subcube of C_i.

The canonical bijection also allows us to regard a restriction of a linear ordering on [k]^n
to any -subcube as a linear ordering on [k]^d.
Namely, let  be a linear ordering on [k]^n and let p be a canonical -parameter
word of length n. If w,w'∈ [k]^d, we then set w w' whenever p w p w'.

Given a linear ordering < on [k], the lexicographic ordering on [k]^n is defined
by setting w<_ w' whenever w_i<w_i', where i is the least index such that w_i≠ w_i'.
Note that if p is a canonical -parameter word, then w<_w' holds for w,w'∈ [k]^d
if and only if p w <_ p w'. Hence, under the canonical bijection,
a restriction of a lexicographic ordering to a -subcube is a lexicographic ordering 
on [k]^d.



For every d there exists n with the following property: for every linear ordering 
of [2]^n there is a -subcube C of [2]^n such that the restriction of  to C 
is the lexicographic ordering for one of the two linear orderings of [2].

<ref> is an easy consequence of <ref>. Indeed, let m=3^n
and define the projection map π [2]^n→ [m] by π(w)∑_i=1^n w_i3^n-i.
The sequence a_1,…,a_m then induces a linear ordering on [2]^n, where
w w' whenever a_π(w)<a_π(w'). A lexicographically ordered -subcube
of [2]^n then corresponds to a monotone subsequence of a_1,…,a_n whose index set is 
a proper affine -cube.



  
Hales–Jewett-type result for general [k]^n.
The naive generalization of <ref> to the case of [k]^n, with k≥ 3,
is false. As an example, define a linear ordering  on [3]^n as follows:
for a word w let w_12 be the word obtained from w by replacing each 1
by 2, and set w w' if either w_12<_ w'_12
or w_12=w'_12 and w<_ w'. This ordering is different
from any of the 3! lexicographic orderings, and is stable under restriction
to subcubes.

To describe the class of linear orderings that generalize the lexicographic ordering
for k≥ 3, we need a couple of auxiliary definitions. A Schröder tree
is a rooted plane[A plane tree is a tree in which children of a node
are ordered.] tree each of whose internal nodes has at least 2 children. A weakly decreasing
Schröder tree is a Schröder tree with a binary relation  on the set of internal nodes that satisfies:


  *  is a total preorder, i.e.,  is transitive, reflexive, and a b or b a for every
two nodes a,b.

  * Every path from the root is strictly decreasing.





[level 1/.style=sibling distance=7em,level 2/.style=sibling distance=5em]
[local bounding box=tree,every node/.style=draw,circle]
(123456) 4
   child  node (123) 3
     child  node (12) 1
       child  [fill] circle (2pt)             
       child  [fill] circle (2pt)             
     
     child  [fill] circle (2pt)      
   
   child   node (4567) 2
     child [sibling distance = 2em]  [fill] circle (2pt)             
     child [sibling distance = 2em]  node(56) 1 
       child [fill] circle (2pt)
       child [fill] circle (2pt)
                 
     child [sibling distance = 2em]  [fill] circle (2pt)             
   ;
[local bounding box=labeled tree,every node/.style=draw,circle,leaf/.style=below,draw=none,execute at begin node=,execute at end node=, xshift=20em]
(1234567) 4
   child  node (123) 3
     child  node (12) 1
       child  [fill] circle (2pt) node[leaf] 2 
       child  [fill] circle (2pt) node[leaf] 4             
     
     child  [fill] circle (2pt) node[leaf] 7      
   
   child   node (4567) 2
     child [sibling distance = 2em]  [fill] circle (2pt) node[leaf] 1 
     child [sibling distance = 2em]  node(56) 1 
       child [fill] circle (2pt) node[leaf] 5
       child [fill] circle (2pt) node[leaf] 6
                 
     child [sibling distance = 2em]  [fill] circle (2pt) node[leaf] 3             
   ;
(labeled caption) [node distance=8ex, below=of labeled tree,text width=5cm,anchor=south] Same, with leaves ordered by
2<4<7<1<5<6<3;
[node distance=1ex,anchor=south] at (tree|-labeled caption) A weakly decreasing Schröder tree;




For a weakly decreasing Schröder tree T, we denote by _T the linear ordering on the internal
nodes of T. If T has k leaves, and we have an linear ordering on [k],
we identify leaves of T with the elements of [k] by labeling leaves in the increasing
order. For a pair of leaves {a,b}∈[k]2
we write [a,b]_T for the bottommost node of T that contains both a and b.

Given a linear ordering < of [k] and a weakly decreasing Schröder tree T with k leaves,
we can define a linear ordering _T on [k]^n as follows. Given two words w,w'∈ [k]^n, we
consider all indices i∈ [n] such that w_i≠ w_i'. Among these, 
we pick the smallest i such that [w_j,w_j']_T _T [w_i,w_i']_T for all j∈ [n].
We then declare w_T w' if w_i<w_i'.


For every k and d there exists n with the following property: for every linear ordering 
of [k]^n there is a -subcube C of [k]^n such that the restriction of  to C 
is equal to _T for some weakly decreasing Schröder tree T with k leaves and some linear ordering of [k].


=13 0cm.860cm.860cm.860cm.860cm.860cm0cm0cm0cm0cm0cm0cm0cm For
-11ex
[scale=0.5,every node/.style=draw,circle,transform shape] 

 (123) 2
 child  node 1
   child [fill] circle (2pt)
   child [fill] circle (2pt)
  
 child [fill] circle (2pt)
 ;
  
example, the ordering on [3]^n above is obtained from the tree depicted on the right,
under the usual ordering 1<2<3. Another ordering on [3]^n can be obtained by taking a mirror image of the tree on the right.
The usual lexicographic ordering is obtained by taking T=
[baseline=-1.1ex,scale=0.38,every node/.style=draw,circle,transform shape,level distance=3ex,sibling distance=1em] 
 (123) 
  child [fill] circle (2pt)
  child [fill] circle (2pt) 
  child [fill] circle (2pt);. In general, Bodini, Genitrini and Naima <cit.> showed that the number 
of weakly decreasing Schröder trees with k leaves is 
equal to the (k-1)'st ordered Bell number, and hence is asymptotic to (k-1)!/2(ln 2)^k.



  
An extension of Ramsey's theorem.
Interestingly, after proving the main result in this paper (<ref>), we found that 
there is another way to prove <ref>, which relies on an extension of Ramsey's theorem.

For every d and r, there exists m such that for every r-edge-coloring of the complete graph on [m]
there is a monochromatic proper affine -cube.

It is easy to deduce <ref> from <ref>: Given a sequence a_1,…,a_m 
we color edge {i,j}, with i<j, with one of two colors according to whether a_i<a_j or a_j<a_i.
A monochromatic clique in this coloring then corresponds to a monotone subsequence.



  
Paper organization.
The bulk of the paper is occupied by the proof of <ref>,
which is split into two parts. We first show that, for any linear ordering  of [k]^n,
there is a large subcube C such that the restriction of  to C enjoys a certain symmetry property,
which we call uniformity. For k=2, the uniform linear orderings are then easily seen to be lexicographic, 
which proves <ref>. That is done in <ref>. The case of general k requires a
more careful analysis of uniform linear orderings, which we carry out in <ref>. 
We conclude the paper with the proof of <ref> in <ref> and with some open problems
in <ref>.



  
Acknowledgment. We thank James Cummings for comments on the earlier version of this paper.



§ UNIFORM LINEAR ORDERINGS

Given a linear ordering  on [k]^n, a restriction of  to a -subcube induces,
under the canonical bijection, one of (k^d)! linear orderings on [k]^d. We say that 
is -uniform if all restrictions to -subcubes induce the same linear ordering
on [k]^d. An ordering that is d-uniform for all d is called simply uniform.


For every k and d there exists n with the following property: for every linear ordering
 of [k]^n there is a -subcube C of [k]^n such that the restriction of  to C 
is uniform.

We shall deduce this from the following special case of the Graham–Rothschild theorem <cit.> 
(see also <cit.> for a transparent exposition and a short proof).

For every d,D,k,t there exists n=n(d,D,k,t) such that, for any t-coloring of -subcubes of [k]^n,
there is a D-subcube of [k]^n all of whose -subcubes are monochromatic.


Let χ be the coloring of -subcubes of [k]^n in (k^d)! many colors that
assigns to each -subcube C the restriction of  to C.
By the Graham–Rothschild theorem, if n is large enough, there is a (2d-1)-subcube
C_0 of [k]^n on which χ is monochromatic. We use the canonical bijection to identify
this subcube with [k]^2d-1. Let C be the subcube of C_0 induced by the canonical word
1…1*_1*_2…*_d (with d-1 many 1's).
We claim that the restriction of  to C is uniform.

Indeed, let C' be an arbitrary d'-subcube C' of C. We can then complete C' to a -subcube C_0' of C_0
in such a way that C' is the subcube of C_0' induced by the canonical word 1…1*_1…*_d'.
In this way every d'-subcube C' is identified with the same d'-subcube of [k]^d, and so
is ordered in the same way.


If  is uniform, with slight abuse of notation, we think of  as a linear ordering
on each [k]^d for d=1,2,…. In particular,  induces an ordering on [k],
which we denote <. The following implies <ref>.

Let  be a uniform linear ordering on [k]^n, for n≥ 3. Suppose a,b∈ [k] satisfy
a<b. Then the restriction of  to {a,b}^n is the lexicographic ordering
for the restriction of < to {a,b}.


We claim that abba. Indeed, if baab, then we reach a contradiction
by considering the sequence of inequalities

    aabbababaaab,

where the first inequality follows because a b, whereas the last two follow because baab.

To show that the restriction of  to {a,b}^n coincides with the lexicographic ordering
on {a,b}^n, it suffices to show w w' whenever w' is the successor of w
in the lexicographic ordering. If w=a^n, then w'=a^n-1b,
and w w' because ab. Otherwise w=w_0ab^t and
w'=w_0ba^t for some nonnegative integer t and a word w_0. In that case
w w' because ab^tba^t follows from abba.




§ THE PROOF OF <REF>

By <ref>, it suffices to show that every uniform linear ordering is of the form
_T for some weakly decreasing Schröder tree T and some linear ordering < on [k]. 
By permuting the elements of [k] if necessary, we may assume that the restriction of the uniform linear ordering
to [k] coincides with the usual ordering on . Hence, in this section < denotes the usual ordering on [k].

Call a subinterval of [k] nontrivial if it is of length at least 2.
Given a linear ordering  on [k]^n, we define a binary relation  on nontrivial subintervals of [k]
as follows. For any a,b,c,d∈ [k] with a< b and c< d,
we write [ a,b]  [ c,d] if
cbda. If both [ a,b]  [ c,d]
and [ c,d]  [ a,b] hold, then we write 
[ a,b ] ≈ [ c,d ].

Note that if =_T, then [ a,b ]  [ c,d ] holds
if and only if [ a,b]_T _T [ c,d]_T holds. 
Furthermore, if =_T, then  satisfies the following three properties:


  * Transitivity: [ a,b ]  [ c,d ] and
[ c,d ]  [ e,f ] together imply
[ a,b ]  [ e,f ].

  * Comparability: [ a,b ]  [ c,d ] or [ c,d ]  [ a,b ].

  * Ultrametric property: if a<b<c, then [ a,c ]≈max([ a,b ],[ b,c ]).

Call any relation  on nontrivial subintervals of [k] tree-like if it satisfies these three properties.
Given a uniform linear ordering on [k]^n, we first show that  is tree-like, and then use  to build
a weakly decreasing Schröder tree. That is done in the next two lemmas. Then in <ref>, we show that the ordering
induced by the resulting tree (almost) coincides with the original ordering on [k]^n.

 Suppose n≥ 3. If a linear ordering  on [k]^n is uniform,
then  is tree-like.


Transitivity: By the assumption we have cbda and edfc.
From this it follows that edbfcbfda, which implies that ebfa by uniformity.

Comparability: Suppose [ a,b ] [ c,d ], and so dacb.
Also, <ref> tells us that {c,d}^n is ordered lexicographically, implying that cbddbc. 
Hence, dadcbddbc, which is to say adbc.

Ultrametric property: We first show that max([ a,b ],[ b,c ]) [ a,c ].
We have abacca, and so [ a,b ][ a,c ]. Similarly,
acbccb, and so [ b,c ] [ a,c ].

We next show that [ a,c ]max([ a,b ],[ b,c ]).
Suppose [ a,c ][ a,b ]. Then baac, and so
bcaacccaa, and hence [ a,c ] [ b,c ].


For a relation  on the nontrivial subintervals of [k] and a weakly decreasing Schröder tree
T, we abuse notation and write =_T provided 
[a,b] [c,d] holds if and only if [a,b]_T_T [c,d]_T holds.


For every tree-like ordering  on [k]2 there exists a 
weakly decreasing Schröder tree T such that =_T.

In a weakly decreasing Schröder tree T we may have
[a,b]_T≈_T [c,d]_T for two reasons: either
because [a,b]_T=[c,d]_T, or neither of [a,b]_T
and [c,d]_T is a descendant of one another, and they happen to be equal
in the _T preorder. Therefore, to build a tree out of a tree-like ordering,
we need to distinguish these two situations. We achieve this by identifying the node
with the widest interval that generates it.

For a nontrivial subinterval [a,b] 
of [k], let a' be the least element of [k] such that [a',b]≈ [a,b].
Likewise, let b' be the largest element of [k] such that [a,b']≈ [a,b].
Define [a,b] [a',b'].

Let 𝒩{[a,b] : ab}. We shall take 𝒩 
be the set of nodes of our tree. To show that we indeed obtain a tree, we must prove that
every two intervals from 𝒩 are either disjoint or one of them contains the other. 
To do this we first show two basic properties of the map [a,b]↦[a,b].

Claim 1: [a,b]≈ [a,b] for every {a,b}∈[k]2. Indeed, suppose [a,b]=[a',b'].
If either a=a' or b=b', then the claim follows. Say a'<a<b<b'.
From the ultrametric property for the triple a'<a<b' we deduce that either
[a',b']≈ [a,b'] or [a',b']≈ [a',a]. In the former case
[a,b]≈ [a,b']≈ [a',b']=[a,b], proving the claim.
In the latter case, two applications of the ultrametric property yield 
[a',b']≈ [a',a] [a',b] [a',b'], 
and so [a',b']≈ [a',b]≈ [a,b] as well.

Claim 2: [a,b]= [a,b] for every {a,b}∈[k]2.
Indeed, suppose [a,b]=[a',b'] and [a,b]=[a”,b”].
Then by two applications of Claim 1 it follows that [a”,b] [a”,b”]≈ [a',b']≈ [a,b],
which, by the minimality of a', implies that a”=a'. Similarly, b”=b'.

We are now ready to prove that every pair of intervals in 𝒩 is either disjoint or comparable.
Let [a,b] and [c,d] be any two intervals from 𝒩,
and suppose that they are not disjoint. Say c≤b (the case a≤d is analogous, and can be
reduced to this case by swapping the roles of the two intervals). If we also have c≤a, then the interval
[c,d] contains [a,b]. So, assume that a<c. By Claim 2 we may
assume that a is the minimal a' such that [a',b]≈ [a,b],
and similarly for b,c,d. From the minimality of c we infer that [a,d]≉[c,d].
By the ultrametric property applied to the triple a<c<d, it follows that [a,d]≈ [a,c].
By another application of the ultrametric property, this time to a<c<b, we infer that
[a,c] [a,b], and so
[a,d] [a,b]. The ultrametric property of a<b<d then implies
that [a,d]≈ [a,b], and so b≥d by the maximality of b.
Hence, [c,d] is contained in [a,b].

It follows that intervals in 𝒩 naturally form a tree under the containment relation.
The tree is plane, with intervals ordered in the natural way. We add leaves to the tree by
declaring that leaf a is a descendant of all intervals that contain a.
For tree nodes [a,b],[c,d]∈𝒩, we order them [a,b]_T [c,d]
if and only if [a,b] [c,d].
The ultrametric property then ensures that every path from the root is decreasing.
Denote the resulting weakly decreasing Schröder tree by T.

Recall that [a,b]_T is the bottommost node of T containing a and b.
Since a,b∈[a,b], it follows that
[a,b]_T⊆[a,b]. On the other hand,
[a,b]⊆ [a,b]_T, which implies that
[a,b]⊆[a,b]_T=[a,b]_T.
So, [a,b]_T = [a,b] for every {a,b}∈[k]2
from which =_T follows.


The last ingredient in the proof of <ref> is the next result. 

If T is a weakly decreasing Schröder tree with k leaves, and  is a uniform linear ordering on [k]^n such that = _T,
then  is equal to _T on every (n-1)-subcube of [k]^n.

Note that, for the reason that will become clear from the proof, we do not assert that = _T. 
<ref> nonetheless follows as we may restrict to a subcube of one dimension smaller.

It suffices to show that w w' whenever w_T w' and w,w' differ in t≤ n-1 positions.
The proof is by induction on t. The case t=1 holds because our assumption that the ordering on [k] is the same for 
 and _T. The case t=2 holds because = _T. So, assume that t≥ 3.

For ease of notation we identify the t-subcube of [k]^n containing both w and w' with [k]^t.
This way, w and w' differ in every position. Let i be the smallest natural number 
such that [w_j,w_j']_T _T [w_i,w_i']_T for all j∈ [n]. Note that w_i<w_i' because w_T w'.

The symbol w_i breaks w into three parts, the prefix, the symbol w_i itself, and the suffix. The prefix and
the suffix cannot be both empty. Suppose first that the prefix is non-empty; we then write w and w' as

    w   =' w_i-1w_i,
    
    w'   =' w_i-1'w_i''

for some words ,'∈ [k]^i-2 and ,'∈ [k]^n-i.
If w_i-1 w_i-1', then w w_i-1' and
since w_i-1'  w' by the induction hypothesis,
the inequality w w' follows. So, we may assume that w_i-1' w_i-1.

Because t≤ n-1 and  is uniform,
the inequality w w' will follow once we show that 
ww', where

    w   ' w_i-1w_iw_i,
    w'   ' w_i-1'w_i'w_i''.


The definition of i implies that [w_i,w_i']_T_T [w'_i-1,w_i-1]_T. Hence, 
[w_i,w_i'][w'_i-1,w_i-1], which is to say w_i-1w_i w'_i-1w_i'.
Therefore,
w w'_i-1w_i' w_i.
On the other hand, w'_i-1w_i' w_i ' w' follows from the uniformity of  and the induction hypothesis applied to the words
w_i and ' w_i' '. Together these imply ww'. 

If the prefix of w (before w_i) is empty, we write

    w   =w_iw_i+1,
    
    w'   =w_i'w_i+1'',

and define

    w   =w_iw_iw_i+1,
    w'   =w_i'w_i'w_i+1''.

Because [w'_i+1,w_i+1]_T _T [w_i,w_i']_T, we have [w'_i+1,w_i+1]  [w_i,w_i'],
and so w_iw_i+1 w_i'w_i+1'. Since the induction hypothesis tells us that 
w_i w_i'', we have ww',
and so w w' in this case as well.




§ EXTENSION OF RAMSEY'S THEOREM

In this section, we prove <ref>. 

Let n=n(2d,2,2,2) be as in the Graham–Rothschild theorem,
and set m=3^n. Let χ[m]2→ [r] be an
r-coloring of the edges of K_m. Define the projection map π [2]^n→ [m]
by π(w)∑_i=1^n w_i3^n-i. The coloring χ of [m]2 then induces a
coloring χ' of [2]^n2 via χ'(w,w')χ(π(w),π(w')).
We can then define a 2-coloring of 2-subcubes of [2]^n as follows.
Let C be any 2-subcube. We identify it with [2]^2 with the aid of the canonical bijection.
Then χ”(C) is equal to the χ'-color of the edge {01,10}.

By the Graham–Rothschild theorem, there is a 2d-subcube C on which χ” is monochromatic.
Call pair of words w,w' incomparable if there exist both i∈ [n] such that (w_i,w_i')=(0,1)
and j∈ [n] such that (w_j,w_j')=(1,0). Since χ” is monochromatic,
every two incomparable words in C are of the same color.

Identify C with [2]^2d, and consider the set 

    S{w∈ [2]^2d : w_2i-1≠ w_2i for all i=1,2,…,d}.

Though S is not a -subcube, its image under the map π is an affine -cube.
Since every two words in S are incomparable, it follows that π(S) 
is monochromatic.




§ OPEN PROBLEMS



  * Conlon and Kamčev <cit.> showed that for every r-coloring of [3]^n there are monochromatic
lines whose wildcard set is a union of at most r intervals (see also <cit.> for a strengthening
for even r). We do not know if one can find a combinatorial line whose wildcard set is an arithmetic progression.


  * In this paper we made no effort to obtain good quantitative bounds. The right dependence of m on d
in <ref> is probably doubly exponential.



plain

