Coupon collectors, q-binomial coefficients and the unsatisfiability threshold

Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou, Malvina Vamvakari, Michele Zito

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the (experimentally observed) abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. An upper bound of 4.506 was announced by Dubois et al. in 1999 but, to the best of our knowledge, no complete proof has been made available from the authors yet. We consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we explain how the method of local maximum satisfying truth assignments can be combined withresu lts for coupon collector’s probabilities in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. Thus, we improve over the best, with an available complete proof, previous upper bound, which was 4.596. In order to obtain this value, we also establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients) which may be of independent interest.

Original languageEnglish (US)
Title of host publicationTheoretical Computer Science - 7th Italian Conference, ICTCS 2001, Proceedings
EditorsAntonio Restivo, Simona Ronchi Della Rocca, Luca Roversi
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783540454465
StatePublished - 2001
Event7th Italian Conference on Theoretical Computer Science, ICTCS 2001 - Torino, Italy
Duration: Oct 4 2001Oct 6 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th Italian Conference on Theoretical Computer Science, ICTCS 2001

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Coupon collectors, q-binomial coefficients and the unsatisfiability threshold'. Together they form a unique fingerprint.

Cite this