3
$\begingroup$

We call a collection ${\cal S}\subseteq {\cal P}(\newcommand{\N}{\mathbb{N}}\N)$ bijection-proof if for any bijection $\varphi:\N\to\N$ there is $T\in{\cal S}$ with $\varphi(T) \in {\cal S}$.

For any set $X$, let $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$. For any positive integer $n\in\N$, we set $[n]^2 :=[\{1,\ldots,n\}]^2$. Trivially $[\N]^2$ is bijection-proof. Let ${\frak B}$ be the collection of bijection-proof subsets of $[\N]^2$.

For $P\subseteq [\N]^2$, we let $$\newcommand{\mmu}{\mu_{[\N]^2}}\mmu(P) = \lim\inf_{n\to\infty}\frac{\newcommand{\card}{\text{card}}\card\big(P\cap [n+1]^2\big)}{\card\big([n+1]^2\big)},$$where of course $\card([n]^2) = n(n-1)/2$ for any positive integer $n$.

Question. What is $\inf\{\mmu(B): B\in {\frak B}\}$?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I suspect randomly choosing pairs with any nonzero probability works, so the infimum is 0, but I'm not sure how to prove this $\endgroup$
    – Daniel Weber
    Commented Jun 10 at 8:45
  • $\begingroup$ You may consider more generally $$\mu_\alpha(P):=\liminf_{n\to\infty}\frac{\text{card}(P\cap[\mathbb N]^2)}{n^{2\alpha}}$$ for $\alpha>0$ $\endgroup$
    – Pietro Majer
    Commented Jun 10 at 10:35
  • 2
    $\begingroup$ @PietroMajer 1001's example has $|P\cap[n+1]^2|=n$, and a simple counting argument shows that any bijection-proof $P$ has $|P\cap[n+1]^2|\ge n/\sqrt2$, lest a random permutation on $[n+1]$ give a counterexample. Thus, the interesting choice is $\alpha=1/2$. $\endgroup$
    – Emil Jeřábek
    Commented Jun 10 at 15:32

1 Answer 1

Reset to default
6
$\begingroup$

Note that $\left\{\{1,a\} \mid a \in \mathbb{N}_{>1}\right\}$ is bijection-proof and $\mu_{\left[\mathbb{N}\right]^2}\left(\left\{\{1,a\} \mid a \in \mathbb{N}_{>1}\right\}\right) = 0$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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