שמור ב:
| מחבר ראשי: | |
|---|---|
| פורמט: | Recurso digital |
| שפה: | אנגלית |
| יצא לאור: |
Zenodo
2025
|
| נושאים: | |
| גישה מקוונת: | https://doi.org/10.5281/zenodo.16776949 |
| תגים: |
הוספת תג
אין תגיות, היה/י הראשונ/ה לתייג את הרשומה!
|
תוכן הענינים:
- <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>