The neighborhood-tour conjecture for ASEP vertices
Let be the asymmetric subtour elimination polytope, let be a vertex of this polytope, and let denote its neighborhood in the vertex structure considered by the paper. A tour is a Hamiltonian cycle of the complete directed graph on the node set. Neighborhood-tour conjecture. For every vertex , the neighborhood contains at least one tour. This is presented as a conjecture based on preliminary computational tests; the supplied text does not establish it or indicate a resolution.
References
- Eleonora Vercesi, Janos Barta, Luca Maria Gambardella, Stefano Gualandi and Monaldo Mastrolilli, “On the integrality Gap of Small Asymmetric Traveling Salesman Problems: A Polyhedral and Computational Approach”, arXiv:2506.10671 (2025).
Progress summary
The conjecture was proposed in 2025, and an unverified 2026 submission claims a counterexample in eight dimensions, while the six- and seven-dimensional cases are said to remain open.
Vercesi, Barta, Gambardella, Gualandi, and Mastrolilli proposed that every vertex of the asymmetric subtour-elimination polytope has a Hamiltonian tour among its neighboring vertices. Their paper reports computational evidence but does not prove the conjecture.
Known results
- Complete enumeration for found the expected neighborhood property.
- For , every vertex had an adjacent representative from each equivalence class.
- Exhaustive neighborhood enumeration was infeasible for , so the general conjecture remained unproved.
Community submission (unverified), November 7, 2026
A submitted argument claims that a fractional vertex of is adjacent to none of the tours, thereby refuting the conjecture at . It states that and remain open, but this claim has not been independently verified here.
Current status (as of November 2026): The conjecture is unproved in the published record; an unverified submission claims it is false for , with and unresolved.
Sources
Solutions 1
A vertex of the asymmetric subtour elimination polytope on eight nodes that is adjacent to no tourSee full solution
Result and scope. Vercesi-Barta-Gambardella-Gualandi-Mastrolilli (arXiv:2506.10671) Conjecture 1 states that every vertex of P_ASEP^n has a tour in its neighbourhood. The fractional vertex x*=X/4 of P_ASEP^8 (19 support arcs, 8 tight cuts, rank 56) is adjacent to none of the 5040 tours: for each tour an integer direction certificate shows that [x*,T] is not a face. The conjecture fails at n=8; n=6,7 remain open.
Complete proof: A vertex of the asymmetric subtour elimination polytope on eight nodes that is adjacent to no tour · PDF.
The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.
This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.