Critical hypergraphs and interesting set-pair systems
type: Item
instance of: scholarly article
title: Critical hypergraphs and interesting set-pair systems
zbMATH Open document ID: 0586.05029
DOI: 10.1016/0095-8956(85)90043-7
published in: Journal of Combinatorial Theory. Series B
publication date: 1985-01-01T00:00:00Z
review text: 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 hyp…
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3939395
zbMATH Keywords: hypergraphs
zbMATH Keywords: pairs of sets
zbMATH Keywords: intersection property
zbMATH Keywords: intersecting set-pair system
zbMATH Keywords: critical hypergraphs
author: Zsolt Tuza
reviewed by: B. Andrasfai
MaRDI profile type: Publication
full work available at URL: 0095-8956(85)90043-7
OpenAlex ID: W1994539900
cites work: On generalized graphs
cites work: Q5331500
cites work: Interpolation of functions over a measure space and conjectures about memory
cites work: Q3284375
cites work: A Problem in Graph Theory
cites work: Q4074927
cites work: An extremal problem for two families of sets
cites work: Q5338785
cites work: Upper bound on the order of tau-critical hypergraphs
cites work: Q5642587
cites work: Q4052170
cites work: Solution of a problem of A. Ehrenfeucht and J. Mycielski
cites work: τ–Critical Hypergraphs and the Helly Property
cites work: Q3708049
cites work: Q4133994
cites work: Q4180391
cites work: Q4055644
cites work: Q4177585
cites work: Q3218170
cites work: Helly-type hypergraphs and Sperner families
cites work: Q3708835
Recommended article: Critical sets in bipartite graphs
Recommended article: Q4326638
Recommended article: Matching criticality in intersecting hypergraphs
Recommended article: Critical independent sets and König-Egerváry graphs
Recommended article: Q4326650
Recommended article: Matching critical intersection hypergraphs
Recommended article: Gallai theorems for graphs, hypergraphs, and set systems
Recommended article: On some conjectures concerning critical independent sets of a graph
Recommended article: Q3708835
Recommended article: Decomposable and indecomposable critical hypergraphs
description: scientific article; zbMATH DE number 3939395