A spectral bound on hypergraph discrepancy
A spectral bound on hypergraph discrepancy
复制标题
超图差异的谱界
DOI：
10.4230/lipics.icalp.2020.93
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Aditya Potukuchi
中科院分区：
文献类型：
--
作者：
Aditya Potukuchi
设$\mathcal{H}$是关于$n$顶点和$m$边的$t$-正则超图。设$M$是$数学{H}$的$m次n$关联矩阵，记为$lambda=max_{v\perp\overline{1}，v=1}mv$.我们证明了$\mathcal{H}$的偏差为$O(\Sqrt{t}+\lambda)$。作为推论，这给出了对于每个$t$，具有$n$顶点和$m\geq n$边的随机$t$-正则超图的差值几乎肯定是随着$n$的增长而为$O(\Sqrt{t})$。该证明还给出了一个多项式时间算法，该算法以超图为输入，在上述保证下输出着色。
Let $\mathcal{H}$ be a $t$-regular hypergraph on $n$ vertices and $m$ edges. Let $M$ be the $m \times n$ incidence matrix of $\mathcal{H}$ and let us denote $\lambda =\max_{v \perp \overline{1},\|v\| = 1}\|Mv\|$. We show that the discrepancy of $\mathcal{H}$ is $O(\sqrt{t} + \lambda)$. As a corollary, this gives us that for every $t$, the discrepancy of a random $t$-regular hypergraph with $n$ vertices and $m \geq n$ edges is almost surely $O(\sqrt{t})$ 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.