4
$\begingroup$

Question: Let $\varepsilon>0$ and $N\in\omega$ be sufficiently large (depending on $\varepsilon$). Let $h:\subseteq N\rightarrow N$ be such that $h(B)\notin B$ for all $B\subsetneq N$. Must there be $B_0\subsetneq B_1\subseteq N$ such that $|B_1|\leq \varepsilon N$ and $h(B_0)=h(B_1)$?

More generally,

Let $a\in\omega,\varepsilon>0$ and $N\in\omega$ be sufficiently large (depending on $a,\varepsilon$). Let $h:\subseteq N\rightarrow N$ be such that $h(B)\notin B$ for all $B\subsetneq N$. Must there be $B_0\subsetneq B_1\subsetneq\cdots\subsetneq B_{a-1}\subseteq N$ such that $|B_{a-1}|\leq \varepsilon N$ and $h(B_0)=\cdots= h(B_{a-1})$?

$\endgroup$

1 Answer 1

5
$\begingroup$

No, this is false if $\varepsilon<1/2$. Here is the construction for one $h$ that satisfies the conditions:

Let $h(B)$ be the $|B|$-th smallest element of $N\setminus B$.

This way if $B_1\subsetneq B_2$, then $h(B_1)<h(B_2)$.

$\endgroup$
1
  • $\begingroup$ Your argument is very nice. $\endgroup$ Commented Jun 5, 2021 at 7:50

You must log in to answer this question.

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