文章基本信息

标题：A Spectral Bound on Hypergraph Discrepancy
本地全文：下载
作者：Aditya Potukuchi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：93:1-93:14
DOI：10.4230/LIPIcs.ICALP.2020.93
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Let â"< be a t-regular hypergraph on n vertices and m edges. Let M be the m Ã- n incidence matrix of â"< and let us denote Î» = max_{v â^^ ðY^âY,} 1/â-vâ- â-Mvâ-. We show that the discrepancy of â"< is O(â^St + Î»). As a corollary, this gives us that for every t, the discrepancy of a random t-regular hypergraph with n vertices and m â¥ n edges is almost surely O(â^St) as n grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.
关键词：Hypergraph discrepancy; Spectral methods; Beck-Fiala conjecture