Signed clique expectation decay conjecture

From papers

Let kk and pp be fixed, let G(n,p,d)\mathcal{G}(n,p,d) denote the noisy high-dimensional random geometric graph model without edge subsampling, and let τ[k]\tau_{[k]} be the signed kk-clique statistic on vertices [k][k]. Signed clique expectation decay conjecture. There exists a constant Ck,pC_{k,p} such that

EG(n,p,d)[τ[k]]Ck,pdk/6.\left\lvert\operatorname{\mathbb{E}}_{\mathcal{G}(n,p,d)}[\tau_{[k]}]\right\rvert \le \frac{C_{k,p}}{d^{k/6}}.

The conjecture would sharpen the dependence on dd in the bound for the expected signed clique count and suggests that signed clique statistics cannot improve the detection boundary in the regimes discussed above. Its resolution is not given in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Suqi Liu and Miklos Z. Racz, “Phase transition in noisy high-dimensional random geometric graphs”, arXiv:2103.15249 (2021).

Solutions 0

No solutions have been posted yet.