The Phase Transition of Discrepancy in Random Hypergraphs
The Phase Transition of Discrepancy in Random Hypergraphs
复制标题
随机超图中差异的相变
DOI：
--
复制
发表时间：
2021
影响因子：
0.8
通讯作者：
X. Pérez
中科院分区：
文献类型：
--
作者：
Calum MacRury;Tomáš Masařík;Leilani Pai;X. Pérez
Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on $n$ vertices and $m$ edges. In the first (edge-independent) model, a random hypergraph $H_1$ is constructed by fixing a parameter $p$ and allowing each of the $n$ vertices to join each of the $m$ edges independently with probability $p$. In the parameter range in which $pn
ightarrow infty$ and $pm
ightarrow infty$, we show that with high probability (w.h.p.) $H_1$ has discrepancy at least $Omega(2^{-n/m} sqrt{pn})$ when $m = O(n)$, and at least $Omega(sqrt{pn loggamma })$ when $m gg n$, where $gamma = min{ m/n, pn}$. In the second (edge-dependent) model, $d$ is fixed and each vertex of $H_2$ independently joins exactly $d$ edges uniformly at random. We obtain analogous results for this model by generalizing the techniques used for the edge-independent model with $p=d/m$. Namely, for $d
ightarrow infty$ and $dn/m
ightarrow infty$, we prove that w.h.p. $H_{2}$ has discrepancy at least $Omega(2^{-n/m} sqrt{dn/m})$ when $m = O(n)$, and at least $Omega(sqrt{(dn/m) loggamma})$ when $m gg n$, where $gamma =min{m/n, dn/m}$. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy in both models (when $p=d/m$), in the dense regime of $m gg n$. Specifically, we apply the partial colouring lemma of Lovett and Meka to show that w.h.p. $H_{1}$ and $H_{2}$ each have discrepancy $O( sqrt{dn/m} log(m/n))$, provided $d
ightarrow infty$, $d n/m
ightarrow infty$ and $m gg n$. This result is algorithmic, and together with the work of Bansal and Meka characterizes how the discrepancy of each random hypergraph model transitions from $Theta(sqrt{d})$ to $o(sqrt{d})$ as $m$ varies from $m=Theta(n)$ to $m gg n$.
Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on $n$ vertices and $m$ edges. In the first (edge-independent) model, a random hypergraph $H_1$ is constructed by fixing a parameter $p$ and allowing each of the $n$ vertices to join each of the $m$ edges independently with probability $p$. In the parameter range in which $pn
ightarrow infty$ and $pm
ightarrow infty$, we show that with high probability (w.h.p.) $H_1$ has discrepancy at least $Omega(2^{-n/m} sqrt{pn})$ when $m = O(n)$, and at least $Omega(sqrt{pn loggamma })$ when $m gg n$, where $gamma = min{ m/n, pn}$. In the second (edge-dependent) model, $d$ is fixed and each vertex of $H_2$ independently joins exactly $d$ edges uniformly at random. We obtain analogous results for this model by generalizing the techniques used for the edge-independent model with $p=d/m$. Namely, for $d
ightarrow infty$ and $dn/m
ightarrow infty$, we prove that w.h.p. $H_{2}$ has discrepancy at least $Omega(2^{-n/m} sqrt{dn/m})$ when $m = O(n)$, and at least $Omega(sqrt{(dn/m) loggamma})$ when $m gg n$, where $gamma =min{m/n, dn/m}$. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy in both models (when $p=d/m$), in the dense regime of $m gg n$. Specifically, we apply the partial colouring lemma of Lovett and Meka to show that w.h.p. $H_{1}$ and $H_{2}$ each have discrepancy $O( sqrt{dn/m} log(m/n))$, provided $d
ightarrow infty$, $d n/m
ightarrow infty$ and $m gg n$. This result is algorithmic, and together with the work of Bansal and Meka characterizes how the discrepancy of each random hypergraph model transitions from $Theta(sqrt{d})$ to $o(sqrt{d})$ as $m$ varies from $m=Theta(n)$ to $m gg n$.
影响因子：
1
作者：
Altschuler, Dylan J.;Niles‐Weed, Jonathan
通讯作者：
Niles‐Weed, Jonathan
在高维中平衡高斯向量
DOI：
--
发表时间：
2020
期刊：
Proceedings of Machine Learning Research
影响因子：
--
作者：
Turner, Paxton;Meka, Raghu;Rigollet, Philippe
通讯作者：
Rigollet, Philippe