Exact constant found for measuring difference in sets using Jaccard distance
The exact asymptotic constant in the metric dimension of Jaccard space
Discrete Mathematics
Summary
The paper studies how to uniquely identify subsets of a large set using a special way of measuring how different they are, called the Jaccard distance. Previously, scientists knew roughly how many reference points were needed to do this, but the exact number was unknown. The authors determined the precise constant that describes this number as the size of the original set grows very large. They connected this problem to a classic puzzle about weighing coins to find defective ones and used known solutions from that puzzle to get exact answers. This work improves our understanding of measuring and distinguishing collections in a mathematically precise way.
Jaccard distancemetric dimensionpower setErdős–Rényi coin-weighing problemdetecting matricesset differenceentropycombinatoricsdistance measurementcardinality
Authors
Bjørn Kjos-Hanssen
Abstract
Let $X$ be a finite set with $|X|=n$ and let $\mathrm{Jac}(a,b)=|a\,\triangle\, b|/|a\cup b|$ be the Jaccard distance on the power set $2^X$. Lladser and Paradise recently proved that the metric dimension of $(2^X,\mathrm{Jac})$ is $Θ(n/\ln n)$, with the constant left open; their bounds are $(\ln 2)\,n/\ln n\lesssim β(2^X,\mathrm{Jac})\lesssim 2\ln(2e)\,n/\ln n$. We determine the constant: \[ β(2^X,\mathrm{Jac})=\frac{2n}{\log_2 n}\,(1+o(1))=(2\ln 2)\,\frac{n}{\ln n}\,(1+o(1)). \] The proof identifies the problem, on each ``slice'' of subsets of fixed cardinality, with the Erdős--Rényi coin-weighing problem for a spring scale (the problem of \emph{detecting matrices}). The lower bound is the Erdős--Rényi entropy argument applied to the middle slice; the upper bound follows from the explicit detecting families of Lindström and of Cantor and Mills, augmented by a single extra landmark that reveals cardinality.