Duality and Hereditary König-Egerváry Set-systems

Abstract

A König-Egerváry graph is a graph $G$ satisfying $\alpha (G)+\mu (G)=|V(G)|$, where $\alpha (G)$ is the cardinality of a maximum independent set and $\mu (G)$ is the matching number of $G$. Such graphs are those that admit a matching between $V(G)-\bigcup \Gamma$ and $\bigcap \Gamma$ where $\Gamma$ is a set-system comprised of maximum independent sets satisfying $|\bigcup {\Gamma }^{\prime }|+|\bigcap {\Gamma }^{\prime }|=2\alpha (G)$ for every set-system ${\Gamma }^{\prime }\subseteq \Gamma$; in order to improve this characterization of a König-Egerváry graph, we characterize \emph{hereditary König-Egerváry set-systems} (HKE set-systems, here after). An \emph{HKE} set-system is a set-system, $F$, such that for some positive integer, $\alpha$, the equality $|\bigcup \Gamma |+|\bigcap \Gamma |=2\alpha$ holds for every non-empty subset, $\Gamma$, of $F$. We prove the following theorem: Let $F$ be a set-system. $F$ is an HKE set-system if and only if the equality $|\bigcap {\Gamma }_1-\bigcup {\Gamma }_2|=|\bigcap {\Gamma }_2-\bigcup {\Gamma }_1|$ holds for every two non-empty disjoint subsets, ${\Gamma }_1,{\Gamma }_2$ of $F$. This theorem is applied in \cite{hke},\cite{broken}.

6 pages