Some contributions to the minimum representation problem of key systems. In: Dix J, Hegner SJ, editors. Lecture Notes in Computer Science. Vol 3861.; 2006. p. 240-57. Abstract
Some contributions to the minimum representation problem of key systems
Some new and improved results on the minimum representation problem for key systems will be presented. By improving a lemma of the second author we obtain better or new results on badly representable key systems, such as showing the most badly representable key system known, namely of size 2(n(1-c.log n/ log n)), where n is the number of attributes. We also make an observation on a theorem of J. Demetrovics, Z. Furedi and the first author and give some new well representable key systems as well.