CRITICAL DUAL SET-SYSTEMS

The equality vertical bar A - B vertical bar = vertical bar B - A vertical bar holds trivially for each finite sets A, B of the same cardinality. Theorem 0.1 presents a generalization of this fact to every set-system of even cardinality. A set-system Gamma is said to be dual if the equality vertical bar boolean AND Gamma(1) - boolean OR Gamma(2)vertical bar = vertical bar boolean AND Gamma(2 )- boolean OR Gamma(1)vertical bar holds, for each two disjoint non-empty sub-set-systems Gamma(1), Gamma(2) of Gamma. A critical dual set-system is a uniform set-system such that each strictly sub-set-system of this set-system is dual. Theorem 0.1. Let k > 1 be an integer. The following are equivalent: (1) k is even and (2) every critical dual set-system of cardinality k is dual. Corollary 0.2 is an application of Theorem 0.1. For a graph G, alpha(G) denotes the maximal cardinality of an independent set. Omega(G) is the set of independent sets of cardinality alpha(G). mu(G) is the matching number of G. G is a Konig Egervary graph if alpha(G) + mu(G) = vertical bar V(G)vertical bar. Corollary 0.2. G is a Konig Egervaty graph if and only if some subset F of Omega(G) satisfies the following two properties: (a) There is a matching from V(G) - boolean OR F into boolean AND F and b) for every sub-set-system Gamma of F of odd cardinality, there is a partition {Gamma(1), Gamma(2)} of Gamma into two non-empty sub-set-systems such that the following equality holds: vertical bar boolean AND Gamma(1) - boolean OR Gamma(2)vertical bar = vertical bar boolean AND Gamma(2 )- boolean OR Gamma(1)vertical bar.