Closure under common neighbours: confluence, islands and percolation thresholds of the k-void rule
Call a non-adjacent pair of vertices of a graph a k-void if it has at least k common neighbours. The k-void rule adds such pairs as edges, one at a time or in rounds, until none is left; it is the law of privation of steretic logic and a threshold form of triadic closure. We collect the basic theory of this rule and add several results. The final graph does not depend on the order of additions, even in the presence of forbidden pairs, and it decreases with k. For k = 1 every component becomes a clique. For every k the rule never joins two components (islands), and the synchronous process needs at least ceil(log2 d) rounds to link two vertices at distance d, with equality in all cases for k = 1. The fixed points are exactly the k-closed graphs of Fox, Roughgarden, Seshadhri, Wei and Wein; hence a saturated network has at most 3^((k-1)/3) n^2 maximal cliques, which in steretic logic bounds the number of possible maximal fusions. For k = 2 the rule lies between diamond and K4 graph bootstrap percolation, and for general k it dominates K_(k+2) bootstrap percolation, which bounds its critical probability from above. Numerically, in G(n, p) with 100 <= n <= 1600 the critical probability scales as n^(-0.86 +/- 0.02) for k = 2 and n^(-0.71 +/- 0.03) for k = 3. The exact exponents are open.
Authors
- Oleksandr Krol
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24334843
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint