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
Additional Services
| 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 |
