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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Closure under common neighbours: confluence, islands and percolation thresholds of the k-void rule

Oleksandr Krol
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Closure under common neighbours: confluence, islands and percolation thresholds of the k-void rule

Oleksandr Krol
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon