4 papers
Series-parallel extensions and Ehrhart positivity
Yao Li, Sihong Shao
We prove Ehrhart positivity for series-parallel matroids and extend this result to all series-parallel extensions of multi-path matroids. A formula for the Ehrhart coefficients of…
Eulerian-spanning set and coboundary operator: An investigation of maxcut beyond planar graphs
Qiming Fang, Sihong Shao, Yuxuan Wu
Using the concepts of Eulerian-spanning set and coboundary operator, we generalize Hadlock's conversion of the maxcut problem on planar graphs to one on general graphs with non-neg…
Every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian
Sihong Shao, Yuxuan Wu
We prove that every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian, and show that the 6-face condition is tight. Our results push the connectivity con…
The Boolean polynomial polytope with multiple choice constraints
Sihong Shao, Yishan Wu
We consider a class of - polynomial programming termed multiple choice polynomial programming (MCPP) where the constraint requires exact one component per subset of the parti…