# Lower and upper (combinatorial) discrepancy

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

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