Skip to main content
MathOverflow

Return to Answer

added 23 characters in body
Source Link
Sam Zbarsky
Sam Zbarsky
  • 1.2k
  • 6
  • 12

For any $t$, we can get $p$ arbitrarily close to $\frac{2}{t+1}$ (in particular, for $t=2$, this gives $p=2/3-\epsilon$).

Take some large $N$ and let $n=(t+1)N$. For $a\in [t+1]$ and $b\in [N]$, define $h_{a,b}:[t+1]\times [n] \to \mathbb{N}$ by $h_{a,b}(c,d)=\big(a+c\pmod{t+1}\big)N+\big(b+d\pmod{N}\big)$ for any $d\in [N]$ and $c\in [t+1]$ (intuitively, $c$ and $a$ matter more, while $b$ and $d$ are used for tie-breaking). Let $\mathcal{F}=\{h_{a,b}\}$.

Given $f_1,\ldots,f_t$, let $a_i,b_i$ be such that $f_i=h_{a_i,b_i}$. A pigeonhole argument gives us that there must be some $a$ so that $a_i\not\equiv a+1 \pmod{t+1}$ for all $i$ and there is at most one $j$ with $a_j=a$. If there is no such $j$, we pick $g=h_{a,1}$. If such a $j$ exists, we pick $g=h_{a,b_j+1\pmod{N}}$. Then whenever $c=t+1-a$ or $c\equiv t-a\pmod{t+1}$ and $(c,d)\ne(t+1-a,N-b_j)$, we have $g(c,d)>\max(f_1(c,d),\ldots,f_t(c,d))$. Thus we get $p=\frac{2N-1}{(t+1)N}=\frac{2}{t+1}-\frac{1}{(t+1)N}$.

For any $t$, we can get $p$ arbitrarily close to $\frac{2}{t+1}$ (in particular, for $t=2$, this gives $p=2/3-\epsilon$).

Take some large $N$ and let $n=(t+1)N$. For $a\in [t+1]$ and $b\in [N]$, define $h_{a,b}:[t+1]\times [n] \to \mathbb{N}$ by $h_{a,b}(c,d)=\big(a+c\pmod{t+1}\big)N+\big(b+d\pmod{N}\big)$ for any $d\in [N]$ and $c\in [t+1]$ (intuitively, $c$ and $a$ matter more, while $b$ and $d$ are used for tie-breaking). Let $\mathcal{F}=\{h_{a,b}\}$.

Given $f_1,\ldots,f_t$, let $f_i=h_{a_i,b_i}$. A pigeonhole argument gives us that there must be some $a$ so that $a_i\not\equiv a+1 \pmod{t+1}$ for all $i$ and there is at most one $j$ with $a_j=a$. If there is no such $j$, we pick $g=h_{a,1}$. If such a $j$ exists, we pick $g=h_{a,b_j+1\pmod{N}}$. Then whenever $c=t+1-a$ or $c\equiv t-a\pmod{t+1}$ and $(c,d)\ne(t+1-a,N-b_j)$, we have $g(c,d)>\max(f_1(c,d),\ldots,f_t(c,d))$. Thus we get $p=\frac{2N-1}{(t+1)N}=\frac{2}{t+1}-\frac{1}{(t+1)N}$.

For any $t$, we can get $p$ arbitrarily close to $\frac{2}{t+1}$ (in particular, for $t=2$, this gives $p=2/3-\epsilon$).

Take some large $N$ and let $n=(t+1)N$. For $a\in [t+1]$ and $b\in [N]$, define $h_{a,b}:[t+1]\times [n] \to \mathbb{N}$ by $h_{a,b}(c,d)=\big(a+c\pmod{t+1}\big)N+\big(b+d\pmod{N}\big)$ for any $d\in [N]$ and $c\in [t+1]$ (intuitively, $c$ and $a$ matter more, while $b$ and $d$ are used for tie-breaking). Let $\mathcal{F}=\{h_{a,b}\}$.

Given $f_1,\ldots,f_t$, let $a_i,b_i$ be such that $f_i=h_{a_i,b_i}$. A pigeonhole argument gives us that there must be some $a$ so that $a_i\not\equiv a+1 \pmod{t+1}$ for all $i$ and there is at most one $j$ with $a_j=a$. If there is no such $j$, we pick $g=h_{a,1}$. If such a $j$ exists, we pick $g=h_{a,b_j+1\pmod{N}}$. Then whenever $c=t+1-a$ or $c\equiv t-a\pmod{t+1}$ and $(c,d)\ne(t+1-a,N-b_j)$, we have $g(c,d)>\max(f_1(c,d),\ldots,f_t(c,d))$. Thus we get $p=\frac{2N-1}{(t+1)N}=\frac{2}{t+1}-\frac{1}{(t+1)N}$.

Source Link
Sam Zbarsky
Sam Zbarsky
  • 1.2k
  • 6
  • 12

For any $t$, we can get $p$ arbitrarily close to $\frac{2}{t+1}$ (in particular, for $t=2$, this gives $p=2/3-\epsilon$).

Take some large $N$ and let $n=(t+1)N$. For $a\in [t+1]$ and $b\in [N]$, define $h_{a,b}:[t+1]\times [n] \to \mathbb{N}$ by $h_{a,b}(c,d)=\big(a+c\pmod{t+1}\big)N+\big(b+d\pmod{N}\big)$ for any $d\in [N]$ and $c\in [t+1]$ (intuitively, $c$ and $a$ matter more, while $b$ and $d$ are used for tie-breaking). Let $\mathcal{F}=\{h_{a,b}\}$.

Given $f_1,\ldots,f_t$, let $f_i=h_{a_i,b_i}$. A pigeonhole argument gives us that there must be some $a$ so that $a_i\not\equiv a+1 \pmod{t+1}$ for all $i$ and there is at most one $j$ with $a_j=a$. If there is no such $j$, we pick $g=h_{a,1}$. If such a $j$ exists, we pick $g=h_{a,b_j+1\pmod{N}}$. Then whenever $c=t+1-a$ or $c\equiv t-a\pmod{t+1}$ and $(c,d)\ne(t+1-a,N-b_j)$, we have $g(c,d)>\max(f_1(c,d),\ldots,f_t(c,d))$. Thus we get $p=\frac{2N-1}{(t+1)N}=\frac{2}{t+1}-\frac{1}{(t+1)N}$.