โ Scribed by R.G. Jeroslow
No coin nor oath required. For personal study only.
This paper skws that for any su Dset S of vertices of the m-dimensional hypercube, L!!d(S) G P-1 * ~%e.-e ind(SS is the rtMxnwm number of tinear inequz!ities needed to define S. I:'urthermare, for any k in the range 1 c k r? 2n-1, there is an S with ind(S) = k, with the defining inequalities taken $1~ canonical cuts. Other related results ~e included, and all are proven by explicit constructions of the SC'S S or explkrt deCnitior,s 01 such sets by linear inequaIities.
The paper is aimad at researchers in bi_;alt:nt programming, since it prolrides upper bounds WI the perfoirmance of algonlthms which combine several ilinear carmstlaints into one, even when the givers constraints have a particularly simple form.
๐ SIMILAR VOLUMES
We show that the known algorithms used to re-write any first order quantifierfree formula over an algebraically closed field into its normal disjunctive form are essentially optimal. This result follows from an estimate of the number of sets definable by equalities and inequalities of fixed polynomi
Consider a hypercube regarded as a directed graph, with one edge in each direction between each pair of adjacent nodes. We show that any permutation on the hypercube can be partitioned into two partial permutations of the same size so that each of them can be routed by edge-disjoint directed paths.