Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can we rearrange all the real numbers between $0$ and $1$, denote $f(x):(0,1) \rightarrow (0,1)$ (a bijection), such that for $$\forall 0<x_1<x_2<\dots<x_n<1,$$ neither $$f(x_1) <f(x_2) <\dots <f(x_n)$$ nor $$f(x_1)>f(x_2)>\dots>f(x_n)$$ can be hold $(n>3)$. I'd like to see an answer for $n=4$ and $n=5$. Thank you!

share|improve this question
    
Are you looking for a bijection for which that holds for all choices of $x_1\dots x_n$? –  Omnomnomnom Jul 19 '13 at 3:05
    
Wow, this is much less easy for the real interval than the rational. –  Kevin Carlson Jul 19 '13 at 3:09
    
@Omnomnomnom Yes,thanks –  Hecke Jul 19 '13 at 3:12
    
Is this generally possible for finite/countable sets? It doesn't seem obvious that it should be –  Omnomnomnom Jul 19 '13 at 3:19
9  
Doesn't the Erdos-Szekeres theorem say this is impossible (even for the rationals) –  deinst Jul 19 '13 at 4:07
show 4 more comments

1 Answer

up vote 7 down vote accepted

As deinst's link has spectacularly shown, there is a direct link between the question of finding a suitable bijection (per your criteria) and Ramsey theory. Let's start by answering the question on finite sets:


Let $X=\{x_1,\dots ,x_N\}\subset \mathbb R$ with $x_i<x_{i+1}$ be a set of cardinality $N\in\mathbb N$, and let $f:X\to X$ be a bijection. Let $G_f$ be the graph defined as follows:

Draw one node for each $x_i$. For any $i< j$ from $1$ to $N$, we draw an edge $e_{ij}$. If $f(x_i)<f(x_j)$, color the edge red. If $f(x_i)>f(x_j)$, color the edge blue.

Our condition is that neither $$ f(x_{i_1}) <f(x_{i_2}) <\dots <f(x_{i_n}) $$ nor $$ f(x_{i_1}) >f(x_{i_2}) >\dots >f(x_{i_n}) $$ is true for any increasing selection of indices $i_k$. This condition holds iff $G_f$ has no monochromatic complete subgraph on $n$ nodes. Thus, for a given $X$, we only can find a suitable $f$ when $N<R(N,N)$.


With that in mind, Ramsey theory gives us the following results:

  • if $n=3$, we can only find a suitable $f$ if $N<6$
  • if $n=4$, we can only find a suitable $f$ if $N<18$
  • if $n=5$, we can only find a suitable $f$ if $N<49$
  • if $n=6$, we can only find a suitable $f$ if $N<165$

and so on and so forth, following the diagonal entries of this table.

Finally, as was pointed out in the comments: for any $X$ of non-finite cardinality, the Infinite Ramsey's Theorem tells us that we can find infinitely many (increasing) $i_k$ so that

$$ f(x_{i_1}) <f(x_{i_2}) <\dots <f(x_{i_k})<\dots $$ or $$ f(x_{i_1}) >f(x_{i_2}) >\dots >f(x_{i_k})>\dots $$


Note: although every bijection has a corresponding graph, not every possible graph on the $N$ nodes as defined above corresponds to a possible bijection $f:X\to X$. However, there may be a bijection for every graph up to isomorphism. At any rate, it is not clear to me whether, for example, we can find a bijection $f$ on an $X$ containing $5$ elements that will satisfy the condition for $n=3$.


After some investigation, it turns out that there is no suitable bijection on a set of $5$ elements. The conditions I gave above on the number of elements in a set are thus necessary but insufficient to establish the existence of a suitable bijection.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.