Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 3

### Tight bounds and conjectures for the Isolation Lemma

Pages: 447 – 468

DOI: http://dx.doi.org/10.4310/JOC.2018.v9.n3.a2

#### Authors

#### Abstract

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

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

Received 19 November 2015