Evolutionary Families of Sets

Abstract

A finite family of subsets of a finite set is said to be evolutionary if its members can be ordered so that each subset except the first has an element in the union of the previous subsets and also an element not in that union. The study of evolutionary families is motivated by a conjecture of Naddef and Pulleyblank concerning ear decompositions of 1-extendable graphs. The present paper gives some sufficient conditions for a family to be evolutionary.