# Is there a finite family of functions such that the max of any two functions can be dominated by a third?

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).

• Exactly what do you mean by "taking all different values"? – Seva Nov 10 '13 at 10:41
• Is $n$ assumed to be large in terms of $t$? (Otherwise, even the cases $n=1$ and $n=2$ seem to present a problem.) – Seva Nov 10 '13 at 10:52
• Taking all different values means that for any i, j, k, l we have $f_i(k)\ne f_j(l)$. Btw, this condition is in fact redundant, so you can ignore it if you wish. – domotorp Nov 10 '13 at 13:49
• Sorry, I just want to know if there is an n, I don't want all n's, I changed the first line. – domotorp Nov 10 '13 at 13:51
• Just pointing out the obvious: a strong version for $t=2$ and arbitrary $\epsilon$ implies strong version for any $t$. – Lev Borisov Nov 18 '13 at 0:35

I can achieve $t=2$, $n=21$, $|\mathcal{F}|=7$. Every pair from $\mathcal{F}$ is defeated by some other element on $11$ of the $21$ coordinates. For future answer's sake, I propose that we report these parameters as $(t,n,c,p) = (2,21,7,11/21)$. If I am not mistaken, this is the first $(2,n,c,p)$ anyone has reported with $p>1/2$.

Take $G$ to be the $21$ element sub group of $S_7$ given by maps $\mathbb{Z}/7 \to \mathbb{Z}/7$ of the form $x \mapsto ax+b$, with $a \in \{ 1,2,4 \}$. Let $G$ act on $\mathbb{R}^7$ by permuting coordinates. Let $\vec{v} \in \mathbb{R}^7$ have strictly increasing coordinates and let $A$ be the $7 \times 21$ matrix whose columns are the $G$ orbit of $\vec{v}$.

$G$ acts transitively on unordered pairs of distinct elements in $\mathbb{Z}/7$. So it is enough to check the claim for one unordered pair of coordiantes: Say $\{ 1,2 \}$. I find that, in $11$ of the $21$ columns of $A$, the $3$rd entry is greater than the first or second.

I tried this idea with some other permutation groups that are weakly $2$-transitive but not strictly $2$ transitive, but it didn't work for any of the others. (The trouble with strictly $2$-transitive is that for any pair $f$, $g$ in $\mathcal{F}$, we wind up with $f$ and $g$ tied, and $\max(g,h)$ can only be better than $g$, so $f$ never beats $\max(f,g)$.)

For the sake of more amusing conversations, I'll share the story I have in my head: This problem is about Arrow's voting paradox for $t$-faced candidates. Consider $n$ voters and $c$ candidates; the $i$-th coordinate of the $j$-th element of $\mathcal{F}$ is how well voter $i$ likes candidate $j$. If $t=1$, we are just pointing out that there may be no Condorcet winner. To imagine $t=2$, consider a $2$-faced candidate: when talking to voters who prefer $f$'s positions, she says what $f$ would say and, when talking to voters who prefer $g$'s positions, she repeats $g$'s slogans. The question is whether we can find a situation where every $2$-faced candidate loses to some sincere candidate (and by an overwhelming margin.)

• Magical - I wonder how you've found this or if anyone manages to extend/generalize it. – domotorp Nov 27 '13 at 20:01
• Well, found mostly by luck. I wanted a weakly $2$-transitive group action which wasn't strictly $2$-transitive because that reduced from checking $\binom{n}{2}$ dominances to checking one. The easiest example I knew of was $\mathbb{Z}/((p-1)/2) \ltimes \mathbb{Z}/p$ acting on $\mathbb{Z}/p$ for $p$ a prime which is $3 \mod 4$. By good luck, the first parameters I tried worked. I guess it also helped that the Arrow story suggested many voters, few candidates; most people seem to be trying the opposite. – David E Speyer Nov 27 '13 at 21:00
• A strategy for proving a bound of $3/4$, or maybe even $2/3$. Make a directed graph with $n$ vertices and an edge $i \to j$ if the majority of voters prefer $i$ to $j$. Call an edge $i \to j$ a STRONG edge if there is some $j'$ so that $i$ is preferred to $\max(j,j')$. Our hypotheses say there are a lot of strong edges. An easy lemma is that, if $p>2/3$, there are no strong directed triangles. If $p>3/4$, there are no directed triangles with two strong edges. Maybe we can show that this is impossible? – David E Speyer Nov 28 '13 at 2:02

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}$.

• What is $p$? (There is no $p$ in the original question.) What do you mean by "Given $f_1,\ldots, f_t$, let $f_i=h_{a_I,b_I}$"? (If $f_i$ are given, how can you define them?) – Seva Feb 19 '14 at 8:51
• p is take from David Speyer's answer--it's the fraction of inputs on which g>max(f_1,...,f_t). I fixed the phrasing for the other question. – Sam Zbarsky Feb 20 '14 at 22:02
• Hi, I'm sorry but for some reason I've not seen your answer earlier. Very nice construction and this might even be the correct value. I hope it inspires some people to work on the problem. – domotorp Sep 2 '14 at 21:08