Signed clique expectation decay conjecture

About 5 years old · traced to

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

∣E⁡G(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.