2
$\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 http://front.math.ucdavis.edu/1104.2922.)

$\endgroup$
  • 3
    $\begingroup$ I have never seen this. However, proving negative is hard, so this is not an answer. $\endgroup$ – Boris Bukh Jan 31 at 20:11
  • 1
    $\begingroup$ Nice question. Can you clarify what you mean by "how many permutations" are needed? $\endgroup$ – kodlu Jan 31 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 Jan 31 at 21:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.