Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$

share|improve this question
1  
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
1  
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
4  
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

2 Answers 2

up vote 20 down vote accepted

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

share|improve this answer
    
Magical - I wonder how you've found this or if anyone manages to extend/generalize it. –  domotorp Nov 27 '13 at 20:01
3  
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 Speyer Nov 27 '13 at 21:00
3  
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 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}$.

share|improve this answer
    
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 at 8:51
2  
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 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 at 21:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.