✦ LIBER ✦

Some results on the complexity of families of sets

✍ Scribed by Daniel Grieser

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 872 KB
Volume: 88
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90008-p

No coin nor oath required. For personal study only.

✦ Synopsis

Grieser, D., Some results on the complexity of families of sets, Discrete Mathematics 88 (1991) 179-192.

Let 'Y be a property of graphs on a fixed n-element vertex set V. The complexity c(P) is the minimal number of edges whose existence in a previously unknown graph H has to be tested such that it becomes possible to decide whether H has property 9 or not. We investigate properties (in the broader sense of families of sets) whose complexity is much less than the maximum (which is (2) for graph properties).

It is well known that such properties must be representable as a disjoint union of long intervals (in the boolean lattice of graphs on V). We show that, if the number of intervals is not too large, the converse is true as well. We also show that there are graph properties whose complexities differ by at most 4n from any given number between 2n -4 and (;). Finally, we give estimates on the complexity of the scorpion graph property.

📜 SIMILAR VOLUMES

On Some Complexity Characteristics of Im

On Some Complexity Characteristics of Immune Sets

✍ Valeriy K. Bulitko 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 363 KB 👁 1 views

## Abstract We suggest some new ways to effectivize the definitions of several classes of simple sets. On this basis, new completeness criterions for simple sets are obtained. In particular, we give descriptions of the class of complete maximal sets.

Independence number and the complexity o

Independence number and the complexity of families of sets

✍ D.Q. Naiman; H.P. Wynn 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 870 KB

Complexity of Recognizing Equal Unions i

Complexity of Recognizing Equal Unions in Families of Sets

✍ David P. Jacobs; Robert E. Jamison 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 87 KB

A family of sets has the equal union property if there exist two nonempty disjoint subfamilies having equal unions and has the full equal union property if, in addition, all sets are included. Both recognition problems are NP-complete even when restricted to families for which the cardinality of eve

On the Complexity of Analytic Sets

✍ Karel Hrbacek 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 463 KB 👁 1 views

Some results on the existence of large s

Some results on the existence of large sets of t-designs

✍ G. B. Khosrovshahi; R. Tayfeh-Rezaie 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 1 views

## Abstract A set of trivial necessary conditions for the existence of a large set of __t__‐designs, __LS__[N](__t,k,__ν), is $N\big | {{\nu \hskip -3.1 \nu}-i \choose k-i}$ for __i__ = 0,…,__t__. There are two conjectures due to Hartman and Khosrovshahi which state that the trivial necessary condi

Some Infinite Families of Large Sets of

Some Infinite Families of Large Sets of t-Designs

✍ B. Tayfeh-Rezaie 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 98 KB

A set of necessary conditions for the existence of a large set of t-designs, LS[N] (t, k, v), is N |( v&i k&i ) for i=0, 1, ..., t. We show that these conditions are sufficient for N=3, t=2, 3, or 4, and k 8.