Constant-community approximation conjecture for subgraph-counting functions

Let ff be a subgraph-counting function. A symmetric matrix XX is called a block matrix with kk communities if there are a symmetric matrix PRk×kP\in\mathbb{R}^{k\times k} and a partition of the indices into kk disjoint communities such that Xij=P1,2X_{ij}=P_{\ell_1,\ell_2} whenever ii and jj belong to communities 1\ell_1 and 2\ell_2, respectively. The notation Xf\mathcal{X}_f denotes the class used in the paper for the matrices associated with ff.

Constant-community approximation conjecture. There is a constant cc independent of NN, but dependent on the weights βi\beta_i, such that every XXfX\in\mathcal{X}_f is o(n)o(n)-close to a block matrix with no more than cc communities.

This conjecture would strengthen the stated theorem, which gives approximation within δn+5000Cβ2n15/16\delta n+5000C_{\boldsymbol{\beta}}^2n^{15/16} using a number of communities depending on δ\delta. The conjectured bound would use a constant number of communities and an error that is sublinear in nn; the supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Ronen Eldan and Renan Gross, “Exponential random graphs behave like mixtures of stochastic block models”, arXiv:1707.01227 (2018).

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.