Critical hypergraphs and interesting set-pair systems
V(H) and \(E(H)=\{E_ 1,...,E_ m\}\) denote the vertex set and edge set of the hypergraph H, respectively. The rank of H is \(\max \{| E_ i|:1\leq i\leq m\}\) and H is r-uniform if \(| E_ i| =r\) for every, i,1\(\leq i\leq m\). A set \(T\subset V(H)\) is called an s-transversal set if \(E_ i\subset T\) or \(| E_ i\cap T| \geq s\) whenever \(E_ i\in E(H)\). (T is a transversal set if \(T\cap E_ i\neq \emptyset\) for every \(E_ i\in E(H).)\) \(\nu\) (H) is the maximal number of pairwise disjoint edges in H and H is said to be \(\nu\)-critical if the contraction of any edge increases \(\nu\) (H). \(\tau\) (H) denotes the minimal cardinality of a transversal set of H and H is called \(\tau\)-critical if the deletion of an arbitrary edge decreases \(\tau\) (H). This paper presents a method for determining the maximal number of vertices in a given class of hypergraphs. The main idea is that instead of sets (edges) the author considers pairs of sets satisfying a special intersection property as follows. We say that the pairs \((A_ i,B_ i)\), \(i=1,...,m\), form an intersecting set-pair system (ISP-system) if \(A_ i\cap B_ j=\emptyset\) if and only if \(i=j\) whenever \(1\leq i\), \(j\leq m\). An ISP-system is called (a,b)-system if, additionally, \(| A_ i| =a\) and \(| B_ i| =b\) for every \(i\leq m\). By the help of this method an upper bound is obtained for the number of vertices, as the pairs of an (a,b)-system cannot cover too many points. The author applies this technique for various problems. He deals with \(\nu\)-critical hypergraphs of rank r and improves the order of magnitude in a result of Lovász. So he gains the best possible estimate, apart from a constant factor, in case \(\nu =1\). Also, for the lower bound, he gives a new construction which has more vertices than the previous ones. The author investigates the connection between ISP-systems and \(\tau\)- critical hypergraphs and gives an upper bound on the number of vertices in r-uniform \(\tau\)-critical hypergraphs which is near to the best for every fixed \(\tau\). Finally he examines a problem concerning s- transversals which is related to the Helly-property. The paper contains also open problems.
scientific article; zbMATH DE number 3939395
scientific article