English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Let $S \subseteq \{0,1\}^n$ and $R$ be any polytope contained in $[0,1]^n$with $R \cap \{0,1\}^n = S$. We prove that $R$ has bounded Chv\'atal-Gomoryrank (CG-rank) provided that $S$ has bounded notch and bounded gap, where thenotch is the minimum integer $p$ such that all $p$-dimensional faces of the$0/1$-cube have a nonempty intersection with $S$, and the gap is a measure ofthe size of the facet coefficients of $\mathsf{conv}(S)$.  Let $H[\bar{S}]$ denote the subgraph of the $n$-cube induced by the verticesnot in $S$. We prove that if $H[\bar{S}]$ does not contain a subdivision of alarge complete graph, then both the notch and the gap are bounded. By our mainresult, this implies that the CG-rank of $R$ is bounded as a function of thetreewidth of $H[\bar{S}]$. We also prove that if $S$ has notch $3$, then theCG-rank of $R$ is always bounded. Both results generalize a recent theorem ofCornu\'ejols and Lee, who proved that the CG-rank is bounded by a constant ifthe treewidth of $H[\bar{S}]$ is at most $2$.

Characterizing Polytopes Contained in the $0/1$-Cube with Bounded Chv\'atal-Gomory Rank