← All problems

The neighborhood-tour conjecture for ASEP vertices

1 year old · traced to

Let PASEPnP_{\text{ASEP}}^{n} be the asymmetric subtour elimination polytope, let x\boldsymbol{x} be a vertex of this polytope, and let N(x)\mathcal{N}(\boldsymbol{x}) 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 x\boldsymbol{x}, the neighborhood N(x)\mathcal{N}(\boldsymbol{x}) 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
  1. 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

Refreshed
Open · progress reported

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 n=4n=4 found the expected neighborhood property.
  • For n=5n=5, every vertex had an adjacent representative from each equivalence class.
  • Exhaustive neighborhood enumeration was infeasible for n=6n=6, so the general conjecture remained unproved.

Community submission (unverified), November 7, 2026

A submitted argument claims that a fractional vertex of PASEP8P_{\mathrm{ASEP}}^8 is adjacent to none of the 50405040 tours, thereby refuting the conjecture at n=8n=8. It states that n=6n=6 and n=7n=7 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 n=8n=8, with n=6n=6 and n=7n=7 unresolved.

Sources

Solutions 1

A vertex of the asymmetric subtour elimination polytope on eight nodes that is adjacent to no tourSee full solutionHide 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.