Source-linked AI summary
An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision
Douglas M. Chen
TL;DR
Smith’s conjecture asks whether connectivity forces any two longest cycles to intersect substantially. This paper combines a Ramsey-theoretic refinement of the Turán approach with computer search and proves an Ω(k^8/11) intersection bound, improving the prior Ω(k^2/3) bound.
Problem
Smith’s conjecture asks whether every k-connected graph has any two longest cycles intersecting in at least k vertices, while the general quantitative bound remains below this target.
Method
The proof excludes a subdivision of K4,T, uses Ramsey theory to obtain well-behaved endpoint orderings, and resolves the reduced rerouting cases by computer search.
Results
Ω(k^8/11) vertices is proved as a lower bound on the intersection of any two longest cycles in every k-connected graph with k≥2.
Takeaways & Limitations
The result improves the known Ω(k^2/3) general bound for Smith’s conjecture to Ω(k^8/11).
Takeaways & Limitations
The Turán-type auxiliary graph omits the endpoint order along the cycles, so the proof must handle an enormous family of possible orderings.
Abstract
from arXiv · showhide
Smith's conjecture asserts that in every $k$-connected graph with $k\geq 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an $Ω(k^{8/11})$ bound for this conjecture, improving upon the $Ω(k^{2/3})$ bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement of the traditional Turán-type approach with computer search.
1. Introduction
Smith’s conjecture links graph connectivity to intersections of longest cycles. This paper improves the known general bound to Ω(k^8/11) using a Ramsey-theoretic refinement of the Turán approach and computer search.
- Smith’s conjecture states that any two longest cycles in a k-connected graph intersect in at least k vertices.
- Known general bounds progressed from Ω(k^1/2) to Ω(k^3/5), Ω(k^5/8), and Ω(k^2/3) through successive auxiliary-graph approaches.The cited works used forbidden subgraphs, computational rerouting, supersaturation, and bounds on copies of K2,7.
- The paper improves the exponent from 2/3 to 8/11, yielding the theorem that longest cycles intersect in Ω(k^8/11) vertices.
- The traditional Turán-type auxiliary graph records cycle intersections but not endpoint order, making rerouting vulnerable to tangled orderings.A rerouting valid for one endpoint ordering may split into several smaller disjoint cycles for another.
- The proof excludes a subdivision of K4,T, uses Ramsey theory to extract well-behaved endpoint orderings, and resolves the remaining cases by computer search.The paper formalizes the search in Section 3 and verifies a missing routing claim in Appendix A.
2. Preliminaries and Conventions
The preliminaries construct a bipartite fragment-incidence graph from two longest cycles and joining paths, then introduce subdivision terminology and supporting results.
- The proof assumes two longest cycles X and Y have intersection size m<k, since m≥k already proves the main result.
- Fragments and Joining Paths: X-fragments and Y-fragments are the path components obtained by deleting the common vertex set M from X and Y.
- Fragments and Joining Paths: Joining paths are a maximum family of pairwise vertex-disjoint paths in G−M connecting X−M to Y−M with interiors avoiding X∪Y.
- Fragments and Joining Paths: The fragment incidence graph F is bipartite, with fragments as vertices and joining paths as edges.
- Fragments and Joining Paths: |V(F)|≤2m and |E(F)|≥k−m, while a cycle-exchange argument gives m≥√(k)−1 and recovers the Ω(k^1/2) bound.
- Subdivisions: A subdivision replaces every edge of a graph by an internally disjoint path of length 2; inherited vertices are branch vertices and inserted vertices are subdividing vertices.
- Subdivisions: The paper invokes a theorem of Conlon, Janzer, and Lee giving an edge bound for graphs that exclude subdivisions of complete bipartite graphs.The cited bound is tight when t is sufficiently large compared with s.
3. Proof of Theorem 1.2 and Reduction to Computer Search
The proof reduces Theorem 1.2 to forbidding a sufficiently large subdivided K_{4,T} in the fragment incidence graph. A Ramsey refinement produces a homogeneous K'_{4,8}-arrangement, and a computer-verified even routing then yields two connected 2-regular subgraphs, one of which contains a cycle longer than either original longest cycle.
- Forbidden subgraph reduction: Theorem 3.1 asserts that the fragment incidence graph F contains no K'_{4,T} for an absolute integer T.The proof proceeds by contradiction from such a subdivided complete bipartite subgraph.
- Ramsey refinement: A homogeneous K'_{4,t}-arrangement records ordered X-fragments, ordered Y-fragments, and rooted orientations of the two longest cycles.The arrangement supplies the structured endpoint orders needed for the routing construction.
- Ramsey refinement: Ramsey theory extracts eight A-fragments with identical six-coordinate pair colors from a sufficiently large K'_{4,T}.The number of colors is r=(4!)^2·(2^4)^3·8!, and T is chosen at least 4R_r(8).
- Routing construction: An even routing uses joining paths whose row and column incidences are all even, pairing endpoints within the same X- and Y-fragments.This parity condition ensures the relevant endpoint pairs can be connected by cycle subpaths.
- Routing construction: The constructed graphs Γ1(I) and Γ2(I) are disjoint unions of cycles, and Claim 3.6 supplies an even routing making both connected.A connected 2-regular graph is a single cycle, so the resulting cycle comparison contradicts maximality.
Appendix A. Discussion of Computer Search for Claim 3.6
Appendix A documents the computer-search method used to verify the routing claim.
- Computer search: The computer search is implemented in the ancillary file routing computation.ipynb.The appendix provides implementation details for the verification.
A.1. Cell 1.
The first search cell encodes homogeneous arrangements, filters feasible Y-types, and enumerates normalized even routings using efficient matching-based connectivity tests.
- Arrangement encoding: Each homogeneous K'_{4,8}-arrangement is encoded by (π, ε, σ, η)∈S4×{±1}^4×S8×{±1}^4, separated into X-types and Y-types.The X-type determines relevant X-cycle endpoint orders, while the Y-type determines Y-cycle endpoint orders.
- Arrangement encoding: Only 1,296 valid σ∈S8 permutations are enumerated after rejecting contradictory global orders of the 32 subdividing fragments.The ordering test incrementally removes fragments with no predecessor.
- Routing enumeration: The search stores each even routing as a 32-bit mask and normalizes its occurring second coordinates to an initial segment.The normalization preserves the existence of a suitable routing.
- Connectivity testing: Joining paths are contracted to pseudovertices, reducing connectivity checks to alternating between two perfect matchings.Connectivity is preserved under contraction, and a single alternating cycle certifies connectedness.
- Search organization: The search evaluates every homogeneous K'_{4,8}-arrangement and splits the computation because small even routings cover almost all cases.The remaining cases are handled separately in the second search cell.
A.2. Cell 2.
The second search cell handles the remaining arrangements through a staged search over small and large normalized even routings.
- Small routes: For each X-type, the small-route search tests normalized even routings of sizes 4, 6, 8, and 10, retaining those with connected Γ2(I).For each retained routing, it records the Y-types for which Γ1(I) is connected.
- Small routes: A greedy subcover prunes the retained routings while preserving coverage of all Y-types found by the small-route search.The pruning is repeated independently for each X-type.
- Large routes: The large-route search checks normalized even routings of sizes 12, 14, and 16 only for arrangements unresolved by the small-route search.This abridged second stage avoids repeating cases already covered.
A.3. Cell 3.
The final verification checks the retained routings and confirms that each homogeneous K′4,8-arrangement admits an even routing connecting both Γ1(I) and Γ2(I).
- For each X-type, the verification checks that every retained routing is nonempty, even, and makes Γ2(I) connected.
- For every Y-type, the same routing list contains a routing that makes Γ1(I) connected.
- Each homogeneous K′4,8-arrangement therefore has an even routing making both Γ1(I) and Γ2(I) connected.
A.4. Results.
The computer search returns PASS, establishing Claim 3.6; the full computation takes a few minutes on a standard modern computer.
- PASS from the notebook’s last cell means the computer search has successfully proven Claim 3.6.
- Running the complete notebook takes a few minutes on a standard modern computer.