t-expansive and t-wise intersecting hypergraphs (Q1076693): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01788079 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1966436600 / rank | |||
Normal rank |
Latest revision as of 11:15, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | t-expansive and t-wise intersecting hypergraphs |
scientific article |
Statements
t-expansive and t-wise intersecting hypergraphs (English)
0 references
1986
0 references
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.
0 references
hypergraph generalization
0 references
Gallai's theorem
0 references
factor-critical graphs
0 references