Optimization Online


ChvŠtalís Conjecture Holds for Ground Sets of Seven Elements

Leon Eifler(eifler***at***zib.de)
Ambros Gleixner(gleixner***at***zib.de)
Jonad Pulaj(pulaj***at***zib.de)

Abstract: 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.

Keywords: Exact Rational Integer Programming; Extremal Combinatorics, Maximal Intersecting Families

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: August 2018, ZIB-Report 18-49, Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany

Download: [PDF]

Entry Submitted: 09/05/2018
Entry Accepted: 09/05/2018
Entry Last Modified: 09/05/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society