HEXAGONbeta

Maximal Independent Sets in Long Graph Subdivisions

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Daniel Adam Pyle ↗

Version 1 / Oct 31, 2026 / CC BY 4.0

Abstract

We study maximal independent sets in finite simple graphs whose edges are replaced by paths with prescribed numbers of internal vertices. Using established finite-state transfer methods, we derive an exact boundary-state formula and an explicit leading asymptotic term that factors over the degrees of the original vertices. A graph-uniform relative error bound gives a sufficient condition for this approximation to remain valid when the base graph grows. Under the same condition, the joint membership indicators of the original vertices approach an explicit product of Bernoulli distributions in total variation. For fixed base graphs, we obtain the first adjacency-sensitive correction and a Gaussian limit for the size of a uniformly chosen maximal independent set. A degree-matched construction demonstrates that bounded aggregate error scale does not suffice for uniform degree-sequence universality. Reproducibility materials include exact enumeration, weighted and moment checks, and numerical spectral comparisons.

Provenance statement

Daniel A. Pyle initiated this research project. OpenAI AI systems performed the technical derivations, computational checks, manuscript drafting, and internal review under his direction. The work builds on established finite-state transfer methods and the literature cited in the manuscript. Separate checks refer to separate AI-assisted derivations and implementations, not independent human mathematical verification. The manuscript has not been peer reviewed or formally verified, and originality remains subject to further literature review. Reproducibility materials are available at https://github.com/dapyle11/long-subdivision-independent-sets. The manuscript is released under CC BY 4.0.

Tools used

OpenAI
OpenAI AI assistant (Lyra) for mathematical derivations, drafting, and AI-assisted review; Python 3 for computational verification; LaTeX/pdfLaTeX for manu.

References

  1. L. Dall'Asta, P. Pin, and A. Ramezanpour, Statistical mechanics of maximal independent sets, Physical Review E 80 (2009), 061136. doi:10.1103/PhysRevE.80.061136 (https://doi.org/10.1103/PhysRevE.80.061136). Open preprint: arXiv:0907.3309 (https://arxiv.org/abs/0907.3309).arXivDOI
  2. M. Dod, The Independent Domination Polynomial , preprint (2016), arXiv:1602.08250 (https://arxiv.org/abs/1602.08250).arXiv
  3. S. Jahari and S. Alikhani, On the independent domination polynomial of a graph, Discrete Applied Mathematics 289 (2021), 416--426. doi:10.1016/j.dam.2020.10.019 (https://doi.org/10.1016/j.dam.2020.10.019). Open preprint: arXiv:1808.07369 (https://arxiv.org/abs/1808.07369).arXivDOI
  4. P. L. Krapivsky and J. M. Luck, A renewal approach to configurational entropy in one dimension, Journal of Physics A: Mathematical and Theoretical 56 (2023), 255001. doi:10.1088/1751-8121/acd5bd (https://doi.org/10.1088/1751-8121/acd5bd). Open preprint: arXiv:2302.08852 (https://arxiv.org/abs/2302.08852).arXivDOI
  5. J.-G. Liu, X. Gao, M. Cain, M. D. Lukin, and S.-T. Wang, Computing solution space properties of combinatorial optimization problems via generic tensor networks, SIAM Journal on Scientific Computing 45 (2023), A1239--A1270. doi:10.1137/22M1501787 (https://doi.org/10.1137/22M1501787). Open preprint: arXiv:2205.03718 (https://arxiv.org/abs/2205.03718).arXivDOI
  6. S. Oh, Maximal independent sets on a grid graph , preprint (2017), arXiv:1709.03678 (https://arxiv.org/abs/1709.03678).arXiv

Version history

  1. v1Submitted by Daniel Adam PyleInitial depositCurrentOct 30, 2026