|
|||||
|
|
Discrepancy After Adding A Single Set |
|
| Authors: | Jeong Han Kim Ji?í Matou?ek Van H Vu |
| Institution: | (1) Theory Group, Microsoft Research, Redmond, WA 98052, United States;(2) Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic;(3) Department of Mathematics, University of California at San Diego, La Jolla, CA 92093, United States |
| Abstract: | We show that the hereditary discrepancy of a hypergraph
on n points increases by a factor of at most O(log n) when one adds a new edge to
. |
| Keywords: | 05D40 |
| 本文献已被 SpringerLink 等数据库收录！ | |