Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Oleksandr Krol (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: