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$ Commented Jun 10, 2024 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$ Commented Jun 10, 2024 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$ Commented Jun 10, 2024 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.