Tight bounds and conjectures for the Isolation Lemma

Given a hypergraph $H$ and a weight function $w : V \to \lbrace 1, \dotsc , M \rbrace$ on its vertices, we say that $w$ is isolating if there is exactly one edge of minimum weight $w(e) = \sum_{i \in e} w(i)$. The Isolation Lemma is a combinatorial principle introduced in Mulmuley et al. (1987) which gives a lower bound on the number of isolating weight functions. Mulmuley used this as the basis of a parallel algorithm for finding perfect graph matchings. It has a number of other applications to parallel algorithms and to reductions of general search problems to unique search problems (in which there are one or zero solutions).

The original bound given by Mulmuley et al. was recently improved by Ta-Shma (2015). in this paper, we show improved lower bounds on the number of isolating weight functions, and we conjecture that the extremal case is when $H$ consists of $n$ Singleton edges. we show that this conjecture holds in a number of special cases: when $H$ is a linear hypergraph or is $1$-degenerate, or when $M = 2$.

We also show that the conjecture holds asymptotically when $M \gg n \gg 1$ (the most relevant case for algorithmic applications).

Keywords

isolation lemma, matching

Full Text (PDF format)

Research supported in part by NSF Awards CNS 1010789 and CCF 1422569.

Received 19 November 2015

Published 18 May 2018