Cutting planes cannot approximate some integer programs

For every positive integer ll, we consider a zero–one linear program describing the following optimization problem: maximize the number of nodes in a clique of an nn-vertex graph whose chromatic number does not exceed ll. Although ll is a trivial solution for this problem, we show that any cutting-plane proof certifying that no such graph can have a clique on more than rlrl vertices must generate an exponential in min{l,n/rl}1/4min{l,n/rl}1/4 number of inequalities. We allow Gomory–Chvátal cuts and even the more powerful split cuts. Previously, exponential lower bounds were only known for the case r=1r=1.