| ai.viXra.org > Combinatorics and Graph Theory |
|
 |
| ai.viXra.org > Combinatorics and Graph Theory |
|
|
Previous months:
2025 - 2505(1) - 2508(2) - 2512(1)
2026 - 2601(1) - 2602(3)
Any replacements are listed farther down
[8] ai.viXra.org:2602.0094 [pdf] submitted on 2026-02-19 17:15:36
Authors: Vinicius F. S. Santos
Comments: 45 Pages. (Note by ai.viXra.org Admin: Please cite listed scientific references)
We develop the spectral theory of operators whose eigenvalue structure is governed by the golden ratio φ = (1 +√5)/2. The foundation is the golden resolvent factorisation: for any real symmetric matrix A, λ2I − λA − A2 = (λI − φA) (λI + A/φ). This identity controls the spectrum of golden companion operators, decomposing eigenvalues into transparent pairs (μφ and −μ/φ) and coupled modes (roots of an explicit secular equation), governed by the Galois conjugation φ 7→ −φ−1 of Q(√5)/Q. We establish six main results: (1) the Golden Amplification Theorem, producing the transparent eigenvalue pairs and their eigenvectors; (2) the Secular Equation, a closed-form characteristic polynomial for coupled modes; (3) the Secular Sensitivity Theorem, identifying the secular weight with the coupled eigenvector norm and establishing Lipschitz continuity of coupled eigenvalues in the coupling vector; (4) the Positive Boost Inequality, bounding submatrix spectral radii via nodal-domain restrictions; (5) the Galois Transfer Principle, exactly classifying partition transfer for conjugate eigenvector pairs via the Transfer/Pareto Trichotomy—with automatic spectral dominance for transparent modes and unavoidable Pareto regimes for coupled modes; (6) the Chebyshev Ladder, generalising the amplification ratio to 2 cos(π/(2p+3)) through the cyclotomic fields Q(ζ2p+3)+. The spectral spread of the golden pair equals the generator of the different ideal of Z[φ], connecting the framework to the arithmetic of Q(√5).
Category: Combinatorics and Graph Theory
[7] ai.viXra.org:2602.0026 [pdf] submitted on 2026-02-08 00:53:04
Authors: Vinicius F S Santos
Comments: 17 Pages. (Note by viXra Admin: Parts of the texts are cut off!)
The Erdős—Lovász Tihany Conjecture (1968) asserts that every graph G with χ(G) ≥ s + t − 1 > ω(G) admits a vertex partition into parts with chromatic numbers ≥ s and ≥ t, respectively. We prove the conjecture for the infinite family of pairs (3, k−2) on Mycielski graphs Mk for all k ≥ 5. Our approach is spectral, centred on the golden ratio φ = (1+√5)/2. The pentagon C5—the minimal graph with χ > ω—has adjacency eigenvalues {2, φ−1, φ−1,−φ,−φ}, and this golden spectral structure propagates through the Mycielski construction: the golden ratio’s defining equation μ2 − μ − 1 = 0 arises exactly from the Mycielski eigenvalue relation (Lemma 2.1). We prove the C5-Peeling Existence Theorem: for every Mk (k ≥ 4), a direction in the golden eigenspace peels off a C5 from Mk. The proof is constructive via spectral interferometry: two Mycielski lift paths span a four-dimensional subspace whose layer-control matrix has det = √5, enabling independent phase steering to select a diagonal lift C5—the reverse cycle through alternating address layers. Computationally, the Hoffman margin of this partition is F = φ−3 = √5 − 2 exactly, verified for all k ≤ 12. The key advance is the Golden Sub-Induction (Theorem 1.2): for k ≥ 6, the 1/φ shadow attenuation forces the peeled C5 into the original vertex block of Mk, so the remainder Mk Pk contains Mycielski(Mk−1 Pk−1) as a subgraph, where (Pk)k≥5 is a coherent family of peeled pentagons. Since χ(Mycielski(G)) = χ(G) + 1 for any graph with an edge, this yields the inductive bound χ(Mk Pk) ≥ k − 2. Combined with χ(C5) = 3, this settles the Tihany conjecture for the pair (3, k−2) on Mk for every k ≥ 5—an infinite family of previously open cases.
Category: Combinatorics and Graph Theory
[6] ai.viXra.org:2602.0007 [pdf] submitted on 2026-02-02 19:31:23
Authors: Lucas Aloisio
Comments: 5 Pages.
We revisit the classical Unit Distance Problem posed by Erdős in 1946. While the upper bound of O(n4/3) established by Spencer, Szemerédi, and Trotter (1984) is tight for systems of pseudo-circles, it fails to account for the algebraic rigidity inherent to the Euclidean metric. By integrating structural rigidity decompositionwith the theory of Cayley-Menger varieties, we demonstrate that unit distance graphsexceeding a critical density must contain rigid bipartite subgraphs. We prove a "FlatnessLemma," supported by symbolic computation of the elimination ideal, showing that the configuration variety of a unit-distance K3,3 (and by extension K4,4) in R2 is algebraically singular and collapses to a lower-dimensional locus. This dimensional reduction precludes the existence of the amorphous, high-incidence structures required to sustain the n4/3 scaling, effectively improving the upper bound for non-degenerate Euclidean configurations.
Category: Combinatorics and Graph Theory
[5] ai.viXra.org:2601.0054 [pdf] submitted on 2026-01-14 21:04:10
Authors: Cody Shane Mitchell
Comments: 12 Pages. (Note by ai.viXra.org Admin: Please cite listed scientific references) 8 tables. Computational code available upon request.
We present a comprehensive computational and theoretical analysis of the Erdős-Szemerédi sunflower problem. We compute exact values m(n,3) = 2, 4, 6, 9, 13, 20 for n = 1,...,6—a sequence absent from the literature for the power-set formulation. Our central results establish proven slack in the Naslund-Sawin bound at multiple values: 41.7% at n=3 and 4.5% at n=6. We prove that each local "blocking" tensor has slice rank exactly 2, while the Naslund-Sawin proof implicitly uses factor 3—identifying the precise source of overcounting. We prove a Strong Balance Theorem: in any maximum sunflower-free family, element frequencies satisfy m(n,3) - m(n-1,3) ≤ d_i ≤ m(n-1,3) - 1, implying frequencies lie in approximately [0.33, 0.67]. We establish that admissible monomials satisfy a degree triangle inequality, constraining the polynomial structure. These structural insights, combined with the observed monotonic decay of the ratio |F_max|/NS(n) from 0.84 to 0.42, point to specific directions for asymptotic improvement.
Category: Combinatorics and Graph Theory
[4] ai.viXra.org:2512.0065 [pdf] submitted on 2025-12-18 21:31:53
Authors: Nikolai Makeev
Comments: 26 Pages. In Russian
This work presents the complete formalization of a 52-element dynamical system within a static 8×7 grid — a deterministic system with historical roots. Using the developed Immersion Analysis Method (IAM), we reveal the full internal structure of the system's 90-step cycle. The system decomposes into three invariant classes: three absolutely fixed elements, two exchange pairs (4 elements) that swap at the cycle's midpoint, and a cyclic group of 45 elements (Essence-Orbit 45). We provide the exact predictive formula Element(j, n) = S[(φ(j) + n) mod 45], where S is an experimentally determined sequence of 45 elements, and φ(j) is the initial phase for cell j.All results are verified by computational experiments over 90,000 iterations. A complete Python implementation is provided, making this the first fully reproducible formalization of this system.
Category: Combinatorics and Graph Theory
[3] ai.viXra.org:2508.0016 [pdf] submitted on 2025-08-07 04:37:21
Authors: Liang Chen
Comments: 8 Pages.
The algorithm in this paper is primarily designed to identify a Hamiltonian cycle in graphs confirmed to contain one. The core idea involves removing redundant edges while preserving essential ones; the remaining edges after deletion form the Hamiltonian cycle. The algorithm’s greatest advantage is that it requires no backtracking.
Category: Combinatorics and Graph Theory
[2] ai.viXra.org:2508.0015 [pdf] submitted on 2025-08-07 04:41:43
Authors: Liang Chen
Comments: 7 Pages.
In this paper, only two graphs with identical initial degree sequences are compared, as graphs with different degree sequences can be easily distinguished through simple traversal, rendering further discussion unnecessary.The core idea of this paper is reverse thinking: if two graphs are identical, they can be constructed step-by-step in the same manner, and they can also be deconstructed stepby-step in the same manner, with each deconstruction step producing identical intermediate results.
Category: Combinatorics and Graph Theory
[1] ai.viXra.org:2505.0081 [pdf] submitted on 2025-05-16 03:29:44
Authors: Hisanori Sakamoto
Comments: 11 Pages. In Japanese
This research presents a novel method of deriving the general term of difference sequences that does not use sigma notation. By treating the first and second differences as arithmetic sequences and focusing on the relationships between terms, we developed a direct formula that connects the initial terms and differences. From this formula, we derived a new summation formula with coefficients displaying an elegant pattern of factorial reciprocals. We then generalised this approach to higher-order difference sequences, expressing the general term using binomial coefficients. This method provides an intuitive understanding of difference sequences using only basic sequence knowledge.
Category: Combinatorics and Graph Theory
None