The determinant bound for discrepancy is almost tight

Introduction

Let $V=[n]:=\{1,2,\ldots,n\}$ be a vertex set and $\mathcal{F}=\{F_{1},F_{2},\ldots,F_{m}\}$ be a system of subsets of $V$. The discrepancy of $\mathcal{F}$ is ${\mathop{\rm disc}\nolimits}(\mathcal{F}):=\min_{\chi}{\mathop{\rm disc}\nolimits}(\mathcal{F},\chi)$, where the minimum is over all colorings $\chi\colon V\to\{-1,+1\}$, and {\mathop{\rm disc}\nolimits}(\mathcal{F},\chi):=\max_{i=1,2,\ldots,m}\bigl{|}\sum_{j\in F_{i}}\chi(j)\bigr{|}.

The hereditary discrepancy of $\mathcal{F}$ is

Here $\mathcal{F}|_{J}$ denotes the restriction of the set system $\mathcal{F}$ to the ground set $J$, i.e., $\{F\cap J:F\in\mathcal{F}\}$.

Bounding the discrepancy or the hereditary discrepancy of a particular set system from below is usually challenging. One of the strongest known tools is a result known as the determinant lower bound. To formulate it we define, for a real matrix $A$,

where the maximum is over all $k\times k$ submatrices $B$ of $A$. For a set system $\mathcal{F}$, we put ${\mathop{\rm detlb}\nolimits}(\mathcal{F}):={\mathop{\rm detlb}\nolimits}(A)$, where $A$ is the incidence matrix of $\mathcal{F}$.

For every (finite) set system $\mathcal{F}$ we haveThe bound in [LSV86] is stated without the $\frac{1}{2}$ factor. This has two causes: first, their discrepancy is scaled by $\frac{1}{2}$ compared to ours, and second, in their argument, at one step they seem to be multiplying by $2$ where, in my opinion, one should divide by 2. ${\mathop{\rm herdisc}\nolimits}(\mathcal{F})\geq{\textstyle\frac{1}{2}}{\mathop{\rm detlb}\nolimits}(\mathcal{F}).$

Lovász et al. [LSV86] conjectured that the determinant lower bound is tight up to a constant factor, i.e., ${\mathop{\rm herdisc}\nolimits}(\mathcal{F})=O({\mathop{\rm detlb}\nolimits}(\mathcal{F}))$ for all $\mathcal{F}$. This was refuted by an example of Hoffmann,The vertex set in the example is the set of edges of the complete $k$-ary tree $T$ of depth $k$ (so $n\approx k^{k}$). The set system $\mathcal{F}$ is a union $\mathcal{F}_{1}\cup\mathcal{F}_{2}$, where $\mathcal{F}_{1}$ consists of the edge sets of all root-to-leaf paths, and $\mathcal{F}_{2}$ contains, for each non-leaf vertex $v$, the set of the $k$ edges connecting $v$ to its successors. We have ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1})\leq 1$, ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{2})\leq 1$, ${\mathop{\rm detlb}\nolimits}(\mathcal{F})=O(1)$, and ${\mathop{\rm disc}\nolimits}(\mathcal{F})=k\approx(\log n)/(\log\log n)$. See, e.g., [BS95] or [Mat10] for more details. which shows that ${\mathop{\rm herdisc}\nolimits}(\mathcal{F})/{\mathop{\rm detlb}\nolimits}(\mathcal{F})$ can be of order $(\log n)/(\log\log n)$. A construction of Pálvölgyi [Pál10], also presented in Section 5 below, provides the slightly stronger lower bound of $\Omega(\log n)$ for the same quantity.

Here we prove that ${\mathop{\rm herdisc}\nolimits}(\mathcal{F})/{\mathop{\rm detlb}\nolimits}(\mathcal{F})$ cannot be much larger than in these examples, at least if $|\mathcal{F}|$ is bounded by a polynomial function of $n$.

Next, we consider the situation where a set system $\mathcal{F}$ as above is a union of set systems $\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{t}$, and we are interested in bounding ${\mathop{\rm herdisc}\nolimits}(\mathcal{F})$ in terms of the hereditary discrepancies of the $\mathcal{F}_{i}$.

For $t=2$, this problem was raised by Sós (it is cited, e.g., in [LSV86]). She asked whether ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1}\cup\mathcal{F}_{2})$ can be estimated in terms of ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1})$ and ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{2})$ for any two set systems $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ (on the same vertex set). Hoffman’s example mentioned above shows that ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1}\cup\mathcal{F}_{2})$ cannot be bounded by a function of ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1})$ and ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{2})$ alone.

The next theorem shows that a good bound is possible if we also allow for a moderate dependence on $m$ and $n$. Namely, ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1}\cup\mathcal{F}_{2})$ can exceed $\max({\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1}),{\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{2}))$ at most by a factor polylogarithmic in $n$ and $m$, not much more than in Hoffman’s example.A connection of Sós’s question to the tightness of the determinant lower bound was observed in [LSV86], although with a different proof, which would yield a quantitatively weaker result in our setting.

The only previous result in this direction, from [KMV05], shows that if $\mathcal{F}_{2}$ consists of a single set, then ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1}\cup\mathcal{F}_{2})=O({\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1})\log n)$.

Let $\mathcal{F}$ be a system of $m$ sets on $n$ vertices, and let $\mathcal{F}=\mathcal{F}_{1}\cup\mathcal{F}_{2}\cup\cdots\cup\mathcal{F}_{t}$. Then

There exist systems $\mathcal{F}$ of $n$ sets on $n$ points with discrepancy of order $\sqrt{n}$ (e.g., systems derived from Hadamard matrices or random set systems; see, e.g., [Mat10]). If we let $\mathcal{F}_{i}$ be the set system consisting of the $i$th set of such an $n$, $i=1,2,\ldots,n$, then ${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{i})=1$, while ${\mathop{\rm herdisc}\nolimits}(\mathcal{F})=\Omega(\sqrt{n})$. In this sense, the bound in Theorem 3 is tight up to a polylogarithmic factor, including the dependence on $t$.

Theorem 3 is an immediate consequence of Theorems 1 and 2 and of the next linear-algebraic lemma.

Let $A_{1},\ldots,A_{t}$ be real matrices, each with $n$ columns, let $D:=\max_{i=1,2,\ldots,t}{\mathop{\rm detlb}\nolimits}(A_{i})$, and let $A$ be a matrix in which each row is a row of some of the $A_{i}$. Then

In case where some of the ${\mathop{\rm detlb}\nolimits}(A_{i})$ are much smaller than the others, for example, one can obtain a somewhat better upper bound by making finer estimates in the calculation in the proof. However, a general formulation of such a finer bound looks cumbersome, and it seems that in such cases, a similar improvement can usually be achieved by applying the lemma repeatedly in several stages with various values of $D$.

The bound in Lemma 4 is generally tight up to a constant factor; this can be seen from an example similar to the one mentioned below Theorem 3. Namely, let $A$ be an $n\times n$ Hadamard matrix (i.e., a matrix with pairwise orthogonal rows and with $\pm 1$ entries, which is well known to exist for infinitely many values of $n$), and let $A_{i}$ be the single-row matrix made of the $i$th row of $A$, $i=1,2,\ldots,n$. Then, obviously, ${\mathop{\rm detlb}\nolimits}(A_{i})=1$, while ${\mathop{\rm detlb}\nolimits}(A)\geq\det(A)^{1/n}=\sqrt{n}$. Moreover, if we partition the rows of this $A$ into $t$ blocks $A_{1},\ldots,A_{t}$ by $n/t$ rows each, then the Hadamard bound, stating that the determinant of a matrix is at most the product of the Euclidean norms of the rows, implies ${\mathop{\rm detlb}\nolimits}(A_{i})\leq\sqrt{n/t}$. This shows the tightness of Lemma 4 for all $t\leq n$.

Vector discrepancy and Bansal’s algorithm. The proof of Theorem 2 is based on a recent breakthrough—an algorithm of Bansal [Ban10]. The algorithm produces a low-discrepancy coloring of a given set system, using semidefinite programming and a clever randomized rounding strategy. To state the consequence of Bansal’s work that we will use, we first introduce another notion of discrepancy.

where $\|\cdot\|$ is the Euclidean norm. So, for vector discrepancy, one colors by unit vectors instead of $\pm 1$’s. Since a $\pm 1$ coloring can also be regarded as a vector coloring by the vectors ${\bf e}_{1}=(1,0,\ldots,0)$ and $-{\bf e}_{1}$, we have ${\mathop{\rm vecdisc}\nolimits}(\mathcal{F})\leq{\mathop{\rm disc}\nolimits}(\mathcal{F})$.

The hereditary vector discrepancy ${\mathop{\rm hervecdisc}\nolimits}(\mathcal{F})$ is the maximum vector discrepancy of a restriction of $\mathcal{F}$ to a subset $J\subseteq V$.

We conjecture that the claim of Theorem 5 actually holds with $\sqrt{\log(mn)}$ instead of $\log(mn)$. If true, this would yield a similar improvement in Theorem 2 and get close to an asymptotically optimal bound, at least assuming $m$ bounded by a polynomial in $n$.

A dual formulation of the vector discrepancy

Proof. We will use the duality of semidefinite programming. Dualizing a semidefinite program is a routine procedure, but unfortunately, I am not aware of an explicit recipe for the general case in the literature. Rather than converting the relevant semidefinite program to a standard form, it seems more convenient to use a duality theorem for conic programing from Duffin [Duf56], which we now introduce.

Let $V,W$ be real vector spaces (for our purposes we may assume that they are finite-dimensional), each with a scalar product, which we denote by $\langle\cdot,\cdot\rangle$ in both cases. Let $K\subseteq V$ and $L\subseteq W$ be closed convex cones,A convex cone is a convex set $K$ such that ${\bf x}\in K$ implies $\lambda{\bf x}\in K$ for all $\lambda\geq 0$. The dual cone of $K$ is $K^{*}=\{{\bf y}:\langle{\bf x},{\bf y}\rangle\geq 0\mbox{ for all }{\bf x}\in K\}$. A simple property we will often use is $(K\oplus L)^{*}=K^{*}\oplus L^{*}$, where $\oplus$ denotes direct sum; we assume $K\subseteq V$, $L\subseteq W$, where $V,W$ are disjoint vector spaces, and $K\oplus L\subseteq V\oplus W$. let ${\bf b}\in W$ and ${\bf c}\in V$ be vectors, and let $F\colon V\to W$ be a linear map. We consider the primal cone program (P)

Here $F^{T}\colon W\to V$ denotes the adjoint of $F$; if we fix orthonormal bases in $V$ and $W$, then the matrix of $F^{T}$ is the transpose of the matrix of $F$. The duality theorem asserts that if the maximum in (P) is a finite number $\gamma$ and if the set of feasible solutions of (P) has an interior point, then (D) is feasible as well and its minimum equals $\gamma$. (Since (P) and (D) are dual to one another, one can also interchange their role in the theorem.)

In our case, we start with a vector program defining ${\mathop{\rm vecdisc}\nolimits}(\mathcal{F})$, namely,

For the constraint $\|\sum_{j\in F_{i}}{\bf u}_{j}\|^{2}\leq t$, we expand the left-hand side to $\sum_{j,k\in F_{i}}{\bf u}_{j}^{T}{\bf u}_{k}$, and then it translates to

where ${\bf a}_{i}$ is the $i$th row of the incidence matrix $A$ of $\mathcal{F}$, regarded as an $n\times 1$ matrix (so ${\bf a}_{i}{\bf a}_{i}^{T}$ is an $n\times n$ matrix), and $\bullet$ denotes the scalar product of matrices (given by $X\bullet Y=\sum_{i,j}x_{ij}y_{ij}$). The constraint $\|{\bf u}_{j}\|=1$ then reads

where $E_{j}$ is the matrix with $1$ at position $(j,j)$ and s elsewhere.

It remains to verify that the duality theorem can be applied to these (P) and (D). We will check that (D) is bounded and has a feasible interior point. To verify boundedness, which means that $\sum_{j=1}^{n}z_{j}$ cannot be arbitrarily large, we use (1) with ${\bf x}={\bf 1}_{n}$: then the left-hand side is bounded, and so $\sum_{j=1}^{n}z_{j}$ is bounded as well.

For an interior feasible point, we can take, e.g., $w_{1}=\cdots=w_{m}=\frac{1}{2m}$, $z_{1}=\cdots=z_{n}=-1$. Then (1) obviously holds for all ${\bf x}$.

Thus, the duality theorem applies and shows that if ${\mathop{\rm vecdisc}\nolimits}(\mathcal{F})\geq D$, then the maximum in (4) is at least $D^{2}$. This yields the existence of the desired $w_{i}$ and $z_{j}$, and the lemma is proved. $\Box$

Proof of Theorem 2

We begin with a simple and probably standard lemma.

where ${\bf y}[K]$ denotes the $|K|$-component vector $(y_{j}:j\in K)$.

Proof. Let $y_{\rm max}:=\max_{j}|y_{j}|$, and for $i=0,1,2,\ldots$, let $K_{i}:=\{j:|y_{j}|\in(2^{-i-1}y_{\rm max},2^{-i}y_{\rm max}]\}$. The contribution to $\|{\bf y}\|$ of the components of ${\bf y}$ with indices in $K_{i}$ for $i\geq 2\log n$, say, is negligible, and so there exists some $i_{0}$ for which $\sum_{j\in K_{i_{0}}}y_{j}^{2}=\Omega(\|{\bf y}\|^{2}/\log n)$. Then $K:=K_{i_{0}}$ will do. $\Box$

Theorem 2 will follow from Bansal’s result (Theorem 5) and the next lemma.

Let $\mathcal{F}=\{F_{1},\ldots,F_{m}\}$ be a set system on $[n]$ with ${\mathop{\rm vecdisc}\nolimits}(\mathcal{F})=D$. Then ${\mathop{\rm detlb}\nolimits}(\mathcal{F})=\Omega(D/\sqrt{\log n}\,)$.

Proof. We begin with the dual formulation of vector discrepancy from Lemma 6. For more convenient notation, we will write the nonnegative weight $w_{i}$ as $\beta_{i}^{2}$. Moreover, we let $J\subseteq[n]$ consist of the indices $j$ with $z_{j}>0$, and we will use the inequality (1) in Lemma 6 only for vectors ${\bf x}$ that are zero outside $J$. Writing $z_{j}=\gamma_{j}^{2}$ for $j\in J$, we arrive at the inequality

Let $C:=A[*,K]$ be the $m\times k$ incidence matrix of the system $\mathcal{F}|_{K}$ (consisting of the columns of $A$ whose indices belong to $K$), and let $\check{C}$ be the $m\times k$ matrix obtained from $C$ by multiplying the $i$th row by $\beta_{i}$. Then (6) can be rewritten as

where the summation is over all $k$-element subsets $I\subseteq[m]$ and $\check{C}[I,*]$ consists of the rows of $\check{C}$ whose indices lie in $I$.

We have $\det(\check{C}[I,*])=\det(C[I,*])\prod_{i\in I}\beta_{i}$. Setting $M:=\max_{I}|\det(C[I,*])|$, we can rewrite the right-hand side of (7) and estimate it as follows:

where the penultimate inequality follows because every term $\prod_{i\in I}\beta_{i}^{2}$ occurs $k!$ times in the multinomial expansion of $(\beta_{1}^{2}+\cdots+\beta_{m}^{2})^{k}$.

Proof of Theorem 2. By Theorem 5, there is a subset $J\subseteq[n]$ with ${\mathop{\rm vecdisc}\nolimits}(\mathcal{F}|_{J})=\Omega({\mathop{\rm herdisc}\nolimits}(\mathcal{F})/\log(mn))$. Theorem 2 follows by applying Lemma 8 to $\mathcal{F}|_{J}$. $\Box$

Proof of Lemma 4

On the other hand, by the Binet–Cauchy formula, we have

Putting (8), (9), and (10) together, we arrive at

Then we estimate, using the concavity of the function $x\mapsto x\ln(1/x)$ and Jensen’s inequality,

Thus $\det(B)^{1/k}\leq D\sqrt{et}$ as claimed. $\Box$

Remark. The case $t=2$ has a somewhat simpler proof using the Laplace expansion of $\det B$, which asserts that

where the sum is over all $|I|$-element subsets $J\subseteq[k]$, $\overline{I}=[k]\setminus I$, and $\mathop{\rm sgn}\nolimits(I,J)\in\{\pm 1\}$ is a sign depending on $I$ and $J$ in a way that is of no concern for us (see, e.g., [BJN83, Theorem 4.3]).

A bound on ${\mathop{\rm detlb}\nolimits}(A)$ for larger $t$ can also be obtained by iterating this argument, but this method apparently leads only to ${\mathop{\rm detlb}\nolimits}(A)=O(tD)$.

Pálvölgyi’s example

As was pointed out by Pálvölgyi (private communication, 2011), his geometric construction in [Pál10] actually provides a slight quantitative improvement over Hoffman’s example. Translated to the setting of set systems, the construction yields, for every $k\geq 1$, two systems $\mathcal{F}_{1},\mathcal{F}_{2}$ of $k$-element subsets of $[n]$, with $n={2k\choose k}-1<4^{k}$, such that

${\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{1}),{\mathop{\rm herdisc}\nolimits}(\mathcal{F}_{2})\leq 1$, and

under every two-coloring of $[n]$, $\mathcal{F}_{1}\cup\mathcal{F}_{2}$ contains a monochromatic set (and consequently, ${\mathop{\rm disc}\nolimits}(\mathcal{F}_{1}\cup\mathcal{F}_{2})=k$).

Since the construction in [Pál10] is presented geometrically, and property (i) is not entirely obvious, we provide a short self-contained exposition.

I would like to thank Nikhil Bansal for enlightening e-mail discussions concerning his algorithm and for help with dualizing the semidefinite program, and Dömötör Pálvölgyi for explaining me how his construction in [Pál10] improves on Hoffmann’s example.

References