t-expansive and t-wise intersecting hypergraphs (Q1076693): Difference between revisions

A hypergraph generalization of Gallai's theorem about factor-critical graphs is proved: let \({\mathcal H}\) be a family of finite sets consisting of at least 2-element members, and suppose that \({\mathcal H}\) is connected. If \({\mathcal H}\) is t-stable (i.e., \(| \cup {\mathcal H}'| \leq | {\mathcal H}'| +t\) holds for every \({\mathcal H}'\subset {\mathcal H}\), and for all \(x\in \cup {\mathcal H}\) there exists a \({\mathcal H}_ x\subset {\mathcal H}\) with \(x\not\in \cup {\mathcal H}_ x\), \(| \cup {\mathcal H}_ x| =| {\mathcal H}_ x| +t)\) then \(| \cup {\mathcal H}| \leq 2t+1\). If here equality holds then the graph \({\mathcal G}=\{E:\) \(E\subset H\in {\mathcal H}\), \(| E| =2\}\) is a factor-critical graph. This result is applied to determine \(\tau^*(r,t)\) for \(r<3t/2\), where \(\tau^*(r,t)\) denotes the maximum value of the fractional covering number of a t-wise intersecting hypergraph of rank r.