Premium
On discrepancy bounds via dual shatter function
Author(s) -
Matousěk Jiří
Publication year - 1997
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579300011943
Subject(s) - mathematics , bounded function , bipartite graph , combinatorics , set (abstract data type) , function (biology) , simple (philosophy) , upper and lower bounds , point (geometry) , discrete mathematics , set function , graph , mathematical analysis , geometry , philosophy , epistemology , evolutionary biology , computer science , biology , programming language
Recently, it has been shown that tight or almost tight upper bounds for the discrepancy of many geometrically denned set systems can be derived from simple combinatorial parameters of these set systems. Namely, if the primal shatter function of a set system ℛ on an n ‐point set X is bounded by const. m d , then the discrepancy disc (ℛ) = O ( n ( d −1)/2 d ) (which is known to be tight), and if the dual shatter function is bounded by const. m d , then disc( R ) = O ( n ( d − 1 ) / 2 dlog n) . We prove that for d = 2, 3, the latter bound also cannot be improved in general. We also show that bounds on the shatter functions alone do not imply the average ( L 1 )‐discrepancy to be much smaller than the maximum discrepancy: this contrasts results of Beck and Chen for certain geometric cases. In the proof we give a construction of a certain asymptotically extremal bipartite graph, which may be of independent interest.