Hamiltonian Tournaments and Gorenstein Rings

✍ Scribed by Hidefumi Ohsugi; Takayuki Hibi

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 98 KB
• Volume: 23
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.2002.0572

✦ Synopsis

Let G n be the complete graph on the vertex set [n] = {1, 2, . . . , n} and ω an orientation of G n , i.e., ω is an assignment of a direction i → j of each edge {i, j} of G n . Let e q denote the qth unit coordinate vector of R n . Write P (G n ;ω) ⊂ R n for the convex hull of the n 2 points e ie j , where i → j is the direction of the edge {i, j} in the orientation ω. It will be proved that, for n ≥ 5, the Ehrhart ring of the convex polytope P (G n ;ω) is Gorenstein if and only if (G n ; ω) possesses a Hamiltonian cycle, i.e., a directed cycle of length n.