The Ramsey community number $r_\kappa$ is the smallest network size at which a graph is better described by a partition into communities than by no partition, under a prescribed detection rule. On a scale-free graph this question is confounded: a block model can split the network merely to absorb its degree distribution. I compute $r_\kappa$ analytically for the deterministic pseudofractal scale-free web of Dorogovtsev, Goltsev, and Mendes, separating genuine community structure from degree heterogeneity with two closed-form detection rules. Under a plain Bernoulli stochastic block model, the web's natural recursive bipartition is unpreferred while small and breaks at $r_\kappa=1095$ nodes, with a log-evidence growing as $(\ln 3-\tfrac{2}{3}\ln 2)n$. Under a degree-corrected model tested against the configuration-model null, the same partition survives, breaking far earlier at $r_\kappa=42$, with a log-evidence growing as $(2\ln 3-\tfrac{4}{3}\ln 2)n$ -- exactly twice the plain slope, and independent of the prior. Degree correction reverses the ordering of the candidate cuts, demoting the hub-leaf split and elevating the recursive one. Because the web is self-similar, the best description is not two communities but a nested hierarchy: the degree-corrected evidence keeps rising as the partition is refined, and is maximised at of order $\sqrt{n}$ communities of $\sim\sqrt{n}$ nodes. A purely local recursive rule thus builds true hierarchical community structure, over and above the scale-free degree sequence it also produces, in an exactly solvable setting.
Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admitting a center within bounded distance. We study the parameterized complexity of the \emph{unweighted Connected Network Microaggregation} problem, focusing on structural parameters and natural clustering parameters such as the distance bound $d$ and cluster size gap $u-\ell$. We show that, unlike the weighted variant, the unweighted connected problem is fixed-parameter tractable when parameterized by neighborhood diversity, and hence by vertex cover. In contrast, it remains $\mathrm{W[1]}$-hard for more general structural parameters, including vertex deletion to paths, stars, and cliques. These hardness results hold even for every $d\ge 2$ and any fixed gap $u-\ell$, showing that these clustering parameters do not overcome the structural hardness. We further show that adding the cluster size bound $u$ restores tractability for structural parameters such as treewidth and cluster vertex deletion. Moreover, $u$ is essential: the problem remains $\mathrm{W[1]}$-hard when these structural parameters are considered alone. For kernelization, we prove that the problem has no polynomial kernel parameterized by vertex cover unless $\mathrm{coNP}\subseteq\mathrm{NP/poly}$, even when the distance constraint is vacuous. Adding $u$ yields a polynomial kernel for vertex cover, while kernelization remains unlikely for more general structural parameters even when combined with $u$. Finally, we show that the problem is NP-hard on graphs of bounded clique-width.
Ajinkya Gaikwad, Dusan Knop, T. Valla· 0 citations
We study approximate counting and sampling algorithms for the hard-core model on $\Delta$-regular bipartite graphs under a spectral expansion condition. Let $M_G$ be the biadjacency matrix of $G$. For every fixed $\xi\in(0,1)$, we give an FPRAS for the hard-core partition function and an efficient approximate sampler whenever \[ \lambda\leq \frac{1-\xi}{\sigma_2(M_G)}. \] The main idea is to introduce a family of quadratic tilts in the left-right occupation imbalance and show that each tilted measure can be sampled efficiently using Glauber dynamics. A discrete Gaussian identity expresses the original hard-core model as an exact positive mixture of these tilted measures; truncation and simulated annealing then yield efficient counting and sampling algorithms. For the complementary high-fugacity regime, we refine the polymer-model approach and show that the required phase-dominance and cluster expansion conditions follow from the singular-spectrum bound alone. Combining the two regimes, we obtain efficient approximate counting and sampling at every fugacity $\lambda>0$ whenever \[ \sigma_2(M_G)\leq c\left(\frac{\Delta^2}{\log(\mathrm e\Delta)}\right)^{1/3} \] for an absolute constant $c>0$. In particular, this recovers all-fugacity algorithms for random $\Delta$-regular bipartite graphs for all sufficiently large $\Delta$, while providing an efficiently verifiable certificate of their success on a given instance.
For a finite simple graph $G$ with at least one edge, the bondage number $b(G)$ is the least number of edges whose deletion increases the domination number $\gamma(G)$. Teschner conjectured that $b(G)\le \tfrac32\Delta(G)$ for every graph $G$. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with \[ \gamma(G)=6 \qquad\text{and}\qquad b(G)=5. \] The domination number is established by a complete counting argument across the bipartition. An explicit five-edge deletion raises the domination number from six to seven. For the matching lower bound, we give an exact finite certificate: the graph has 297 minimum dominating sets, and deleting any one of its $\binom{27}{4}=17{,}550$ four-edge subsets leaves at least one of those sets dominating. The enumeration is deterministic, uses only exact integer and set operations, and is reproduced by the complete standard-library verifier included in the appendix.
We consider the voter model on the giant component of a hyperbolic random graph, which is a spatial scale-free network, in the sparse and linear-giant regime $\alpha\in(1/2,1)$. We find that the quenched expected consensus time has order $n^{2-1/\alpha}$, as the number of vertices $n\to\infty$, with probability arbitrarily close to one. This is generalised to the voter model where each vertex changes its opinion at rates $q(v)={\rm d}(v)^\varphi$, where we also establish the consensus time orders for all $\varphi\geq 0$. These orders have 3 regimes, with a phase transition at $\varphi=2-2\alpha$. For the upper bounds, our main proof idea is to connect the meeting set to some fixed target vertex of appropriate height in the product chain electrical network, to make rigorous an argument due to Durrett.
It is proved that, as long as $p=o(\log n /n)$, for any $\varepsilon>0$, one can construct a confidence set of vertices of size $K(\varepsilon)$ that depends only on $\varepsilon$ and not on $n$, such that it contains the root with probability at least $1-\varepsilon$.
Luc Devroye, Gábor Lugosi, Neeladri Maitra· 1 citation· ⚡1
We prove an $\mathrm{MSO}_2$ zero-one law for a very sparse Erd\H{o}s-R\'enyi graph after pruning by component order. Let $p_n=c_n/n$, where $c_n\to0$, and delete every component of order less than $f(n)$, where $f(n)\to\infty$. If \[ f(n)\bigl(\log f(n)+\log(1/c_n)\bigr)=o(\log n), \] then the resulting graph satisfies a zero-one law for $\mathrm{MSO}_2$, with quantification over sets of vertices and sets of edges. The proof combines uniform component counts, an MSO Feferman-Vaught decomposition for disjoint unions, and semilinearity of the order spectra of MSO-definable classes of finite trees. We also show that the term $f(n)\log f(n)$ cannot simply be omitted: star components can occur at first-order-visible Poisson thresholds. We further establish first-order limit laws for bond percolation on the discrete torus $T_L^d$. In the two-sided subpolynomial regime, pruning below a sufficiently slow threshold yields a zero-one law. For the unpruned model in either one-sided polynomial regime, the reciprocal exponents $\alpha=1/k$ are precisely the critical scales. At such a scale, an extended limit of $N p_N^k$ or $N q_N^k$ equal to $0$ or $\infty$ gives a zero-one law; a positive finite limit gives a convergence law but not a zero-one law; and the absence of an extended limit gives failure of convergence. Finally, $\mathrm{MSO}_1$ already detects the parity of the torus side length through bipartiteness, producing a natural obstruction to monadic convergence in a near-deterministic regime.
Mostafa Mirabi, S. Shelah· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
