Return to Question

Is it true that for every $t$ there is an $n$ and there exists a finite function family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different values) and for any $f_1, \ldots, f_t \in \cal F$ there is a $g \in \cal F$ such that $g > \max(f_1,\ldots, f_t)$ on

(weak form:) more than $n/2$ inputs,

(strong form:) $(1-\epsilon)n$ inputs (for some small $\epsilon>0$)?

I already don't know the answer for $t=2$, while for $t=1$ it is easy to give such a family. The question is an equivalent formulation of a problem regarding discrete voronoi games (see http://arxiv.org/abs/1303.0523).

Update: Wow, no answers even after the bounty, quite surprising. Meanwhile, Lev Borisov has observed in the comments that if the strong version is true, it is enough to prove it for $t=2$. Seva has posed a weaker (?) version of the problem: "Circular" domination in ${\mathbb R}^4$. The current best bound is due to Sam Zbarsky (see his answer).

Is it true that for every $t$ there is an $n$ and there exists a finite function family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different values) and for any $f_1, \ldots, f_t \in \cal F$ there is a $g \in \cal F$ such that $g > \max(f_1,\ldots, f_t)$ on

(weak form:) more than $n/2$ inputs,

(strong form:) $(1-\epsilon)n$ inputs (for some small $\epsilon>0$)?

I already don't know the answer for $t=2$, while for $t=1$ it is easy to give such a family. The question is an equivalent formulation of a problem regarding discrete voronoi games (see http://arxiv.org/abs/1303.0523).

Update: Wow, no answers even after the bounty, quite surprising. Meanwhile, Lev Borisov has observed in the comments that if the strong version is true, it is enough to prove it for $t=2$. Seva has posed a weaker (?) version of the problem: "Circular" domination in ${\mathbb R}^4$. The current best bound is due to Sam Zbarsky (see his answer).

Here are some somewhat related, potentially useful results:
https://arxiv.org/abs/1504.03602
https://arxiv.org/abs/1601.04146

Is it true that for every $t$ there is an $n$ and there exists a finite function family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different values) and for any $f_1, \ldots, f_t \in \cal F$ there is a $g \in \cal F$ such that $g > \max(f_1,\ldots, f_t)$ on

(weak form:) more than $n/2$ inputs,

(strong form:) $(1-\epsilon)n$ inputs (for some small $\epsilon>0$)?

I already don't know the answer for $t=2$, while for $t=1$ it is easy to give such a family. The question is an equivalent formulation of a problem regarding discrete voronoi games (see http://arxiv.org/abs/1303.0523).

Update: Wow, no answers even after the bounty, quite surprising. Meanwhile, Lev Borisov has observed in the comments that if the strong version is true, it is enough to prove it for $t=2$. Seva has posed a weaker (?) version of the problem: "Circular" domination in ${\mathbb R}^4$

Is it true that for every $t$ there is an $n$ and there exists a finite function family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different values) and for any $f_1, \ldots, f_t \in \cal F$ there is a $g \in \cal F$ such that $g > \max(f_1,\ldots, f_t)$ on

(weak form:) more than $n/2$ inputs,

(strong form:) $(1-\epsilon)n$ inputs (for some small $\epsilon>0$)?

I already don't know the answer for $t=2$, while for $t=1$ it is easy to give such a family. The question is an equivalent formulation of a problem regarding discrete voronoi games (see http://arxiv.org/abs/1303.0523).

Update: Wow, no answers even after the bounty, quite surprising. Meanwhile, Lev Borisov has observed in the comments that if the strong version is true, it is enough to prove it for $t=2$. Seva has posed a weaker (?) version of the problem: "Circular" domination in ${\mathbb R}^4$. The current best bound is due to Sam Zbarsky (see his answer).