2026/07/31 by Pakin Methawisal
Mathematics · Computer Science · #math.CO #cs.DM #msc:05C20 #msc:37B15
20 pages, 6 figures. Strengthened the upper bound, added an improved construction for odd n, expanded the related-work discussion, and streamlined the exposition
arxiv created 2026/08/01 · arxiv updated 2026/08/04
We study synchronous Boolean dynamics on finite loopless directed graphs in which a vertex is active at the next time step exactly when its number of active in-neighbors is prime. We call these systems Pulse Graphs. Let L(n) denote the largest attractor period realizable on n vertices. Exhaustive enumeration gives L(1),…,L(5)=1,1,1,3,9. Our main result determines the exponential order of the maximum period: 2n-3-1≤ L(n)≤2n-n-1 (n≥5). The lower bound is obtained by implementing a maximal-length affine feedback register using prime-count logic gates. For n≥6, the construction is loopless, has maximum in-degree five, and uses only O(n) edges. For odd n≥7, a period-3 control module improves the lower bound to 3(2n-4-1). For complete directed graphs, we derive an exact update formula, classify all attractors as fixed points or complement two-cycles, prove that every orbit reaches its eventual attractor within three updates, and count the attractors explicitly. We also derive the activation probability under independent random inputs. For sparse random directed graphs, the associated prime-Poisson mean-field map undergoes a nondegenerate fold at c_∗≈3.824963, ρ_∗≈0.368241, with local bistability immediately above the threshold.