A Closed-Form Entropy-Based Lower Bound for Diagonal Ramsey Numbers
Fuente:
Zenodo
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Recurso digital |
| Lenguaje: | inglés |
| Publicado: |
Zenodo
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866901532227665920 |
|---|---|
| author | Fathi, Kevin |
| author_facet | Fathi, Kevin |
| contents | <div>We introduce a deterministic framework for deriving lower bounds on the diagonal Ramsey number $R(k,k)$ using symbolic entropy theory, grounded in the formal correspondence between Shannon entropy and Kolmogorov complexity. By encoding 2-edge colorings of the complete graph $K_{n}$ as derivations under a symbolic grammar, we quantify the total symbolic complexity required to forbid monochromatic $K_{k}$ subgraphs. This complexity incorporates both entropy and a grammar-induced degeneracy term $\Delta_{G}(\phi)$. We establish a threshold where this required complexity equals the raw coloring capacity. Applying this framework to a canonical Conjunctive Normal Form (CNF) grammar yields a closed-form, asymptotic lower bound:</div> <div> </div> <div>\[ R(k,k) \gtrsim \left(\frac{k!}{2\alpha_{k}}\right)^{1/(k-2)}, \]</div> <div> </div> <div>where $\alpha_{k}$ is the clause entropy coefficient. While this specific bound is polynomial and thus weaker than classical probabilistic bounds, our result establishes a novel, verifiable, and deterministic methodology. We discuss how optimizing the underlying grammar and generalizing to non-ideal systems offers a structural alternative to probabilistic techniques.</div> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_16776949 |
| institution | Zenodo |
| language | eng |
| publishDate | 2025 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | A Closed-Form Entropy-Based Lower Bound for Diagonal Ramsey Numbers Fathi, Kevin Ramsey theory Diagonal Ramsey numbers Symbolic entropy Clause complexity CNF encoding Combinatorial lower bounds Kolmogorov complexity Extremal graph theory Formal proof methods Entropy-based reasoning Structural irreducibility Non-probabilistic combinatorics Boolean grammars Syntactic encoding Constructive combinatorics <div>We introduce a deterministic framework for deriving lower bounds on the diagonal Ramsey number $R(k,k)$ using symbolic entropy theory, grounded in the formal correspondence between Shannon entropy and Kolmogorov complexity. By encoding 2-edge colorings of the complete graph $K_{n}$ as derivations under a symbolic grammar, we quantify the total symbolic complexity required to forbid monochromatic $K_{k}$ subgraphs. This complexity incorporates both entropy and a grammar-induced degeneracy term $\Delta_{G}(\phi)$. We establish a threshold where this required complexity equals the raw coloring capacity. Applying this framework to a canonical Conjunctive Normal Form (CNF) grammar yields a closed-form, asymptotic lower bound:</div> <div> </div> <div>\[ R(k,k) \gtrsim \left(\frac{k!}{2\alpha_{k}}\right)^{1/(k-2)}, \]</div> <div> </div> <div>where $\alpha_{k}$ is the clause entropy coefficient. While this specific bound is polynomial and thus weaker than classical probabilistic bounds, our result establishes a novel, verifiable, and deterministic methodology. We discuss how optimizing the underlying grammar and generalizing to non-ideal systems offers a structural alternative to probabilistic techniques.</div> |
| title | A Closed-Form Entropy-Based Lower Bound for Diagonal Ramsey Numbers |
| topic | Ramsey theory Diagonal Ramsey numbers Symbolic entropy Clause complexity CNF encoding Combinatorial lower bounds Kolmogorov complexity Extremal graph theory Formal proof methods Entropy-based reasoning Structural irreducibility Non-probabilistic combinatorics Boolean grammars Syntactic encoding Constructive combinatorics |
| url | https://doi.org/10.5281/zenodo.16776949 |