Enumerating facets of Q0/1

Abstract

We present initial findings regarding the study of an external representation of convex polytope Q_0/1 [4] & [9], the convex hull of all n! O(n²) permutation matrices specially extended into O(n⁴) space, the feasible region of a linear program that models the NP-complete Hamilton tour decision problem. A complete set of irredundant facet-defining inequalities of Q_0/1 for n=4 is discovered, and a minimum count of irredundant facet-defining inequalities of Q_0/1 for n=5 is also presented. Facet-defining inequalities of general Q_0/1 are then conjectured, based upon observations noted for n=4 and n=5.