9
$\begingroup$

For any set $X$, let $\newcommand{\N}{\mathbb{N}}[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$ and set $[n]^2 = [\{0,\dotsc,n-1\}]^2$ for any positive integer $n$. For $A\subseteq [\N]^2$ we set $$\newcommand{\mmu}{\mu_{[\N]^2}}\mmu(A) = \liminf_{n\to\infty}\frac{ \operatorname{card}(A\cap [n+1]^2)}{\operatorname{card}([n+1]^2)}.$$

If $f:\N\to\N$ is a bijection, we set $$\DeclareMathOperator{\rev}{rev}\rev(f) =\{p\in[\N]^2:\min(f(p)) = f(\max(p))\}.$$

Is there a bijection $f:\N\to\N$ with $\mmu\big({\rev(f)}\big) = 1$?

Improve this question
$\endgroup$
1
  • $\begingroup$ I was curious about the maximum value that $\newcommand{\N}{\mathbb{N}}\newcommand{\mmu}{\mu_{[\N]^2}}\DeclareMathOperator{\rev}{rev}\mmu\big({\rev(f)}\big)$ can reach, so I asked another question. $\endgroup$
    – Saúl RM
    Commented Jun 13 at 23:54

1 Answer 1

Reset to default
11
$\begingroup$

$\newcommand\N{\mathbb N}$No, it is not possible to have $\mu_{[\N]^2}\big({\operatorname{rev}(f)}\big) = 1$.

Given the function $f$, we will say that $n\in\mathbb{N}$ is good if $f(n)<f(k)$ for more than $\frac{3n}{4}$ values of $k\in\{1,\dots,n-1\}$. If $\mu_{[\N]^2}\big({\operatorname{rev}(f)}\big) = 1$, then the set of good numbers necessarily has density $1$.

So for big enough $N$ there will be more than $2^{N-1}+1$ good numbers in $[2^N,2^{N+1}-1]$. But that poses a problem: let $N$ be big and let $L_N$ be the median of the set of values $\{f(1),\dots,f(2^N-1)\}$. Then, for all good numbers $n\in[2^N,2^{N+1}-1]$ we have $f(n)<L_N$. Thus, $f(n)\leq L$ for at least $2^N$ values in $\{1,\dots,2^{N+1}\}$. Thus $L_{N+1}\leq L_N$. This cannot happen for all $N$, of course, as $\lim_{N\to\infty}L_N=\infty$, so we have a contradiction.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Wonderful @SaulRM! First I was sure there was a positive answer, also in light of bof's comments $\endgroup$
    – Dominic van der Zypen
    Commented Jun 13 at 6:09
  • 4
    $\begingroup$ Now the natural question is, what is the maximum possible $\mu_{[\N]^2}\big({\operatorname{rev}(f)}\big)$? Bof's example showed that it is at least $\frac{1}{2}$, and my proof gives an upper bound $<1$ $\endgroup$
    – Saúl RM
    Commented Jun 13 at 13:49
  • 1
    $\begingroup$ I did ask it in the end, as a separate question (see the comment to the question) $\endgroup$
    – Saúl RM
    Commented Jun 14 at 16:20
  • 1
    $\begingroup$ By the way, perhaps it would have made more sense if you had asked it, @DominicvanderZypen, as the question is essentially yours. I thought you had read my comment and were not planning to ask it yourself, which is why I asked it (as, this question being already answered, I didn't think it would attract much more attention). Perhaps it would make sense to merge the questions? (I don't know how that works) $\endgroup$
    – Saúl RM
    Commented Jun 14 at 16:35
  • 1
    $\begingroup$ That's all right @SaulRM - I was on a longer hike and didn't check the comments. Yes it would be nice to merge the questions, but I doubt it is possible. $\endgroup$
    – Dominic van der Zypen
    Commented Jun 16 at 20:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .