Cones, Lattices and Hilbert Bases of Cuts
Tanmay Deshpande · Summit (Simon Fraser University) · 2013
A Hilbert Basis is defined as a to be a set of vectors $S$ such that every vector in the cone and lattice generated by $S$ can also be expressed as a non negative integer combinations of vectors in $S$. Goddyn (1991) conjectured that characteristic vectors of cuts of graphs form Hilbert Basis. A counter example to this conjecture was given by Laurent in 1996. We study the class of graphs whose cuts form a Hilbert basis and prove that the cuts of graphs formed by uncontractions of $K_5$ and those of $K_{3,3}$-free graphs form Hilbert bases. In addition, we repair an incorrect result of Laurent that says the cuts of all proper subgraphs of $K_6$ form Hilbert bases by proving that the cuts of $K_6 setminus e$ do not form a Hilbert basis. We also study the cones, lattices and Hilbert bases of contractible cycles of projective planar graphs by looking at the cuts of their dual graphs.