4
$\begingroup$

(I will state my question in terms of combinatorial discrepancy, but the same could be also asked about measure-theoretic discrepancy as well.)

The combinatorial discrepancy of a family $\mathcal F$ is defined as $$disc(\mathcal F)=\min_{\chi\to \pm 1} \max_{F\in \mathcal F} |\sum_{x\in F} \chi(x)|=\min_S \max_{F\in \mathcal F} |2|F\cap S|-|F||,$$

i.e., we want $S$ to be even in all sets of $\mathcal F$. What happens if instead we have two families, one in which we want many elements of $S$, and another in which we want few? Define $$disc(\mathcal F_1,\mathcal F_2)=\min_S \max(\max_{F_1\in \mathcal F_1} 2|F_1\cap S|-|F_1|;\max_{F_2\in \mathcal F_2} |F_2|-2|F_2\cap S|).$$

Note that $disc(\mathcal F,\mathcal F)=disc(\mathcal F)$. Has this parameter ever been studied? Are there some interesting results that carry through? For example, how many permutations do we need in $\mathcal F_1$ and $\mathcal F_2$ to have a non-constant $disc(\mathcal F_1,\mathcal F_2)$? (For the related question in case of $disc(\mathcal F)$ the answer is $3$, see https://arxiv.org/abs/1104.2922.)

$\endgroup$
4
  • 3
    $\begingroup$ I have never seen this. However, proving negative is hard, so this is not an answer. $\endgroup$
    – Boris Bukh
    Commented Jan 31, 2019 at 20:11
  • 1
    $\begingroup$ Nice question. Can you clarify what you mean by "how many permutations" are needed? $\endgroup$
    – kodlu
    Commented Jan 31, 2019 at 20:59
  • 2
    $\begingroup$ @kodlu For example a possible answer could be that if $|\mathcal F_1|=1$, then $disc(\mathcal F_1,\mathcal F_2)$ is a constant (depending on $|\mathcal F_2|$), while otherwise it is constant only if $|\mathcal F_1|=|\mathcal F_2|= 2$. $\endgroup$
    – domotorp
    Commented Jan 31, 2019 at 21:05
  • $\begingroup$ Not exactly the same thing, but these two different discrepancies appear in doi.org/10.1007/978-3-540-32439-3_3. $\endgroup$
    – domotorp
    Commented Mar 22, 2019 at 21:04

0

You must log in to answer this question.