The determinant bound for discrepancy is almost tight (2012)

In 1986 Lovász, Spencer, and Vesztergombi proved a lower bound for the hereditary discrepancy of a set system <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in terms of determinants of square submatrices of the incidence matrix of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . As shown by an example of Hoffman, this bound can differ from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal h normal e normal r normal d normal i normal s normal c left-parenthesis script upper F right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">h</mml:mi> <mml:mi mathvariant="normal">e</mml:mi> <mml:mi mathvariant="normal">r</mml:mi> <mml:mi mathvariant="normal">d</mml:mi> <mml:mi mathvariant="normal">i</mml:mi> <mml:mi mathvariant="normal">s</mml:mi> <mml:mi mathvariant="normal">c</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {herdisc}(\mathcal {F})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> by a multiplicative factor of order almost <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log n"> <mml:semantics> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\log n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the size of the ground set of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We prove that it never differs by more than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis left-parenthesis log n right-parenthesis Superscript 3 slash 2 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O((\log n)^{3/2})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , assuming <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue script upper F EndAbsoluteValue"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">|\mathcal {F}|</mml:annotation> </mml:semantics> </mml:math> </inline-formula> bounded by a polynomial in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We also prove that if such an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the union of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t"> <mml:semantics> <mml:mi>t</mml:mi> <mml:annotation encoding="application/x-tex">t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> systems <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F 1 comma ellipsis comma script upper F Subscript t Baseline"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow>