×

On the fractional matching polytope of a hypergraph. (English) Zbl 0779.05030

Let \({\mathcal H}=(V,E)\) be a hypergraph where \(V\) is a finite set and \(E\) is a multiset of subsets of \(V\). A subset \({\mathcal M}\) of \(E\) is called a matching if every two of its members are disjoint, and a function \(w:E\to\mathbb{R}_ +\) is called a fractional matching if \(\sum_{e\in E:v\in e}w(e)\leq 1\) for all \(v\in V\). For \(b:E\to\mathbb{R}_ +\) let \[ \nu_ b=\max\left\{\sum_{e\in{\mathcal M}}b(e):\;{\mathcal M}\text{ is a matching}\right\}, \]
\[ \nu^*_ b=\max\left\{\sum_{e\in E}b(e)w(e):\;w \text{ is a fractional matching}\right\}. \] In the case \(b\equiv 1\) write briefly \(\nu\) and \(\nu^*\). \({\mathcal H}\) is called \(k\)-uniform if \(| e|=k\) for all \(e\in E\), and \({\mathcal H}\) is called intersecting if \(\nu=1\). The following theorems are proved:
(1) Any hypergraph \({\mathcal H}\) has a matching \({\mathcal M}\) with \(\sum_{e\in{\mathcal M}}(| e|-1+{1\over | e|})\geq\nu^*\).
(2) For any \(k\)-uniform hypergraph \({\mathcal H}\) and any \(b:E\to\mathbb{R}_ +\) we have \(\left(k-1+{1\over k}\right)\nu_ b\geq\nu^*_ b\).
(3) If \(w\) is a fractional matching of an intersecting hypergraph \({\mathcal H}\), then \(\sum_{e\in E}w(e){1\over| e|-1+1/| e|}\leq 1\).
(4) If \({\mathcal H}\) is \(k\)-uniform and intersecting, and \(\bigcap_{e\in{\mathcal H}}e=\varnothing\), then \({1\over| E|^ 2}\sum_{e\in E}\sum_{f\in E}| e\cap f|\geq{k^ 2\over k^ 2- k+1}\).
Reviewer: K.Engel (Rostock)

MSC:

05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05D15 Transversal (matching) theory
Full Text: DOI

References:

[1] C. Berge: Packing problems and hypergraph theory: a survey,Ann. Discrete Math. 4 (1979), 3-37. · Zbl 0425.05017 · doi:10.1016/S0167-5060(08)70816-1
[2] B. Bollobás:Extremal Graph Theory, Academic Press, New York/London, 1978.
[3] V. Faber andL. Lovász: Problem 18 in: Hypergraph Seminar (Ohio State Univ., 1972),Lecture Notes in Mathematics 411 p. 284. C. Berge and D. K. Ray-Chaudhuri, Eds., Springer-Verlag, Berlin/New York, 1974.
[4] Z. Füredi: Maximum degree and fractional matchings in uniform hypergraphs,Combinatorica 1 (1981), 155-162. · Zbl 0494.05045 · doi:10.1007/BF02579271
[5] Z. Füredi: Matchings and covers in hypergraphs,Graphs and Combinatorics 4 (1988), 115-206. · Zbl 0820.05051 · doi:10.1007/BF01864160
[6] L. Lovász:Combinatorial Problems and Exercises, Pakadémiai Kiadó, Budapest North-Holland, Amsterdam, 1979.
[7] L. Lovász: Graph theory and integer programming,Ann. Discrete Math 4 (1979), 141-158. · Zbl 0407.05053 · doi:10.1016/S0167-5060(08)70822-7
[8] C. Shannon: A theorem on coloring the lines of a network,J. Math. Physics 28 (1949), 148-151. · Zbl 0032.43203
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.