Chvátal’s Conjecture Holds for Ground Sets of Seven Elements

Please always quote using this URN: urn:nbn:de:0297-zib-70240
  • We establish a general computational framework for Chvátal’s conjecture based on exact rational integer programming. As a result we prove Chvátal’s conjecture holds for all downsets whose union of sets contains seven elements or less. The computational proof relies on an exact branch-and-bound certificate that allows for elementary verification and is independent of the integer programming solver used.

Download full text files

Export metadata

Metadaten
Author:Leon EiflerORCiD, Ambros GleixnerORCiD, Jonad Pulaj
Document Type:ZIB-Report
Tag:exact rational integer programming; extremal combinatorics
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2018/08/28
Series (Serial Number):ZIB-Report (18-49)
ISSN:1438-0064