On the fractional matching polytope of a hypergraph (Q684403): Difference between revisions

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}\).