Laplacian simplices associated to digraphs

Takayuki Hibi (Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Suita, Osaka, Japan)

Marie Meyer (Department of Mathematics, University of Kentucky, Lexington, Ky., U.S.A.)

Akiyoshi Tsuchiya (Department of Pure and Applied Mathematics, Graduate School of Information, Science and Technology, Osaka University, Suita, Osaka, Japan)

Abstract

We associate to a finite digraph $D$ a lattice polytope $P_D$ whose vertices are the rows of the Laplacian matrix of $D$. This generalizes a construction introduced by Braun and the third author. As a consequence of the Matrix-Tree Theorem, we show that the normalized volume of $P_D$ equals the complexity of $D$, and $P_D$ contains the origin in its relative interior if and only if $D$ is strongly connected. Interesting connections with other families of simplices are established and then used to describe reflexivity, the $h^{*}$-polynomial, and the integer decomposition property of $P_D$ in these cases. We extend Braun and Meyer’s study of cycles by considering cycle digraphs. In this setting, we characterize reflexivity and show there are only four non-trivial reflexive Laplacian simplices having the integer decomposition property.

Keywords

lattice polytope, Laplacian simplex, digraph, spanning tree, matrixtree theorem

2010 Mathematics Subject Classification

Primary 52B20. Secondary 05C20.

Full Text (PDF format)

Received 11 October 2017

Received revised 15 March 2018

Accepted 2 April 2018

Published 24 May 2022