Constant-community approximation conjecture for subgraph-counting functions
Constant-community approximation conjecture for subgraph-counting functions
Let be a subgraph-counting function. A symmetric matrix is called a block matrix with communities if there are a symmetric matrix and a partition of the indices into disjoint communities such that whenever and belong to communities and , respectively. The notation denotes the class used in the paper for the matrices associated with .
Constant-community approximation conjecture. There is a constant independent of , but dependent on the weights , such that every is -close to a block matrix with no more than communities.
This conjecture would strengthen the stated theorem, which gives approximation within using a number of communities depending on . The conjectured bound would use a constant number of communities and an error that is sublinear in ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.