Tight bounds and conjectures for the isolation lemma

DOI10.4310/JOC.2018.V9.N3.A2zbMATH Open1387.05196arXiv1604.07035WikidataQ123119356 ScholiaQ123119356MaRDI QIDQ1750661FDOQ1750661

Vance Faber, David G. Harris

Publication date: 23 May 2018

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: Given a hypergraph $H$ and a weight function $w:Vightarrow1,dots,M$ on its vertices, we say that $w$ is isolating if there is exactly one edge of minimum weight $w(e)=su{m}_{iine}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. When $Mggn$ our improved bound matches this extremal case asymptotically. We are able to 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 it holds asymptotically when $Mggngg1$.

Full work available at URL: https://arxiv.org/abs/1604.07035

zbMATH Keywords

matchingisolation lemma

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (1)

• Bipartite Perfect Matching is in Quasi-NC

Recommendations

• Title not available (Why is that?) 👍 👎
• Isolation and lattice embeddings 👍 👎
• Tight Bounds on the Radius of Nonsingularity 👍 👎
• On the strong separation conjecture 👍 👎
• Isolation, matching, and counting uniform and nonuniform upper bounds 👍 👎
• Near optimal bounds in Freiman's theorem 👍 👎
• On the bounded isometry conjecture 👍 👎
• Polynomial-time analogues of isolatedness 👍 👎
• Tight Lower Bounds for Testing Linear Isomorphism 👍 👎
• Isolation, Infima and Diamond Embeddings 👍 👎

This page was built for publication: Tight bounds and conjectures for the isolation lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1750661)