Normality of semigroups with some links to graph theory. (Q2575799): Difference between revisions

Besides the results summarized below, the article provides some overview of related results from earlier researches. Let \(A\) be an integral matrix of order \(n\times q\) with nonzero distinct columns and let \({\mathcal A}=\{v_1,\dots,v_q\}\) be the set of column vectors of \(A\). The `affine semigroup' of \(A\) is defined as: \(\mathbb{N}{\mathcal A}=\mathbb{N} v_1+\cdots+\mathbb{N} v_q\). The `integral closure' or `normalization' of \(\mathbb{N}{\mathcal A}\) is defined as \(\overline{\mathbb{N}{\mathcal A}}=\mathbb{Z}{\mathcal A}\cap\mathbb{R}_+{\mathcal A}\). The semigroup \(\mathbb{N}{\mathcal A}\) is said to be `normal' if \(\overline{\mathbb{N}{\mathcal A}}=\mathbb{N}{\mathcal A}\). An integral matrix \(A\) is `\(t\)-unimodular' if all the nonzero \(r\times r\) minors of \(A\) have absolute value equal to \(t\), where \(r\neq 0\) is the rank of \(A\). After recalling some results about elementary vectors in the kernel of an integral matrix, using Hegler's Theorem and Carathéodory's Theorem it is shown that, if \(A\) is a \(t\)-unimodular matrix, then \(\mathbb{N}{\mathcal A}\) is normal. If \(A\) has nonnegative entries its `Rees semigroup' is \({\mathcal R}:=\mathbb{N}(v_1,1)+\cdots +\mathbb{N}(v_q,1)+\mathbb{N} e_1+\cdots+\mathbb{N} e_n\), where \(e_i\) is the \(i\)-th unit vector of \(\mathbb{R}^{n+1}\). A matrix is said to be `totally unimodular' if every nonzero minor has absolute value equal to 1. Using linear programming techniques it is proved that, if \(A\) is a nonnegative totally unimodular matrix, then \({\mathcal R}(A)\) is normal. Next, the class of affine semigroups coming from incidence matrices of undirected graphs is investigated. It is shown that if \(A_G\) is the incidence matrix of a simple bipartite graph \(G\), then \({\mathcal R}(A)\) is normal. As a corollary of a theorem of Simis et al. and a theorem of Hibi and Oshugi it is shown that the affine semigroup of the incidence matrix \(A_G\) of a connected graph \(G\) is normal if and only if any two vertex disjoint odd cycles are connected by at least one edge of \(G\). Next, a combinatorial description of the edge cone \(\mathbb{R}_+{\mathcal A}_G\) of a graph \(G\) is given. Let \(I\) be an independent set of vertices of \(G\), the supporting hyperplane of the edge cone defined by \(\sum_{v_i\in I}x_i=\sum_{v_i\in N(I)}x_i\) is denoted \(H_I\). For any hyperplane \(H\) its associated positive and negative closed half-spaces are denoted by \(H^+\) and \(H^-\). It is shown, that if \(G\) is a connected graph on \(n\) vertices, then \(\mathbb{R}_+{\mathcal A}_G=(\bigcap_IH^-_I)\cap(\bigcap_{i=1}^nH^+_{e_i})\), where the first intersection is taken over all the independent sets of vertices of \(G\) and \(H^+_{e_i}=\{x\in\mathbb{R}^n\mid x_i\geq 0\}\). In these terms a characterization of the facets of the edge cone is derived. The affine semigroup of the incidence matrix of a bipartite graph is shown to satisfy \(\mathbb{N}{\mathcal A}_G=\mathbb{R}_+{\mathcal A}_G\cap\mathbb{Z}^n\). As an application of the results about normality and the description of the edge cone the Marriage theorem and the Generalized marriage theorem for undirected graphs are derived.