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

Vance Faber (IDA, Center for Computing Sciences, Bowie, Maryland, U.S.A.)

David G. Harris (Department of Computer Science, University of Maryland, College Park, Md., U.S.A.)

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

Full Text (PDF format)

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

Received 19 November 2015