A vertex of the asymmetric subtour elimination polytope on eight nodes that is adjacent to no tour

Myeongjin Kang

Abstract

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.

AI-assisted research preprint. The scoped main statement has a Lean certificate; internal AI review is not external journal peer review. Bounded prior-art searches do not certify worldwide priority. See the paper for qualifications and supplementary results not covered by Lean.

1

Supplementary files

  • proof-sources.json571.3 KBOpen
  • extract_sources.py472 BOpen

Comments

Submitted by Myeongjin Kang. Original AI-assisted research draft and source proof package; draft preparation and internal campaign-status language in the PDF records its preparation stage. Related MathDB problem 368807. 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. Attachments: proof-sources.json preserves UTF-8 source files from the accepted proof archive; extract_sources.py reconstructs them. The original archive SHA-256 is recorded in the JSON.

Version history

Discussion 0