Advances and Applications in Discrete Mathematics
Volume 22, Issue 2, Pages 221 - 242
(November 2019) http://dx.doi.org/10.17654/ |
|
CRITICAL DUAL SET-SYSTEMS
Adi Jarden
|
Abstract: The equality 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 Γ is said to be dual if the equality
holds, for each two disjoint non-empty sub-set-systems of Γ. 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 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, denotes the maximal cardinality of an independent set. is the set of independent sets of cardinality is the matching number of G. G is a König Egerváry graph if
Corollary 0.2. G is a König Egerváry graph if and only if some subset F of satisfies the following two properties:
(a) There is a matching from into and
(b) for every sub-set-system Γ of F of odd cardinality, there is a partition of Γ into two non-empty sub-set-systems such that the following equality holds:
|
Keywords and phrases: König-Egerváry graphs, independent sets, set-systems.
|
|
Number of Downloads: 208 | Number of Views: 834 |
|