A triplet comparison oracle on a set $S$ takes an object $x in S$ and for any pair ${y, z} subset S setminus {x}$ declares which of $y$ and $z$ is more similar to $x$. Partitioned Local Depth (PaLD) supplies a principled non-parametric partitioning o
f $S$ under such triplet comparisons but needs $O(n^2 log{n})$ oracle calls and $O(n^3)$ post-processing steps. We introduce Partitioned Nearest Neighbors Local Depth (PaNNLD), a computationally tractable variant of PaLD leveraging the $K$-nearest neighbors digraph on $S$. PaNNLD needs only $O(n K log{n})$ oracle calls, by replacing an oracle call by a coin flip when neither $y$ nor $z$ is adjacent to $x$ in the undirected version of the $K$-nearest neighbors digraph. By averaging over randomizations, PaNNLD subsequently requires (at best) only $O(n K^2)$ post-processing steps. Concentration of measure shows that the probability of randomization-induced error $delta$ in PaNNLD is no more than $2 e^{-delta^2 K^2}$.
Suppose $V$ is an $n$-element set where for each $x in V$, the elements of $V setminus {x}$ are ranked by their similarity to $x$. The $K$-nearest neighbor graph is a directed graph including an arc from each $x$ to the $K$ points of $V setminus {x}$
most similar to $x$. Constructive approximation to this graph using far fewer than $n^2$ comparisons is important for the analysis of large high-dimensional data sets. $K$-Nearest Neighbor Descent is a parameter-free heuristic where a sequence of graph approximations is constructed, in which second neighbors in one approximation are proposed as neighbors in the next. Run times in a test case fit an $O(n K^2 log{n})$ pattern. This bound is rigorously justified for a similar algorithm, using range queries, when applied to a homogeneous Poisson process in suitable dimension. However the basic algorithm fails to achieve subquadratic complexity on sets whose similarity rankings arise from a ``generic linear order on the $binom{n}{2}$ inter-point distances in a metric space.
We extend the seminal van den Berg-Kesten Inequality on disjoint occurrence of two events to a setting with arbitrarily many events, where the quantity of interest is the maximum number that occur disjointly. This provides a handy tool for bounding u
pper tail probabilities for event counts in a product probability space.
Write $mathcal{C}(G)$ for the cycle space of a graph $G$, $mathcal{C}_kappa(G)$ for the subspace of $mathcal{C}(G)$ spanned by the copies of the $kappa$-cycle $C_kappa$ in $G$, $mathcal{T}_kappa$ for the class of graphs satisfying $mathcal{C}_kappa(G
)=mathcal{C}(G)$, and $mathcal{Q}_kappa$ for the class of graphs each of whose edges lies in a $C_kappa$. We prove that for every odd $kappa geq 3$ and $G=G_{n,p}$, [max_p , Pr(G in mathcal{Q}_kappa setminus mathcal{T}_kappa) rightarrow 0;] so the $C_kappa$s of a random graph span its cycle space as soon as they cover its edges. For $kappa=3$ this was shown by DeMarco, Hamm and Kahn (2013).
An old conjecture of Zs. Tuza says that for any graph $G$, the ratio of the minimum size, $tau_3(G)$, of a set of edges meeting all triangles to the maximum size, $ u_3(G)$, of an edge-disjoint triangle packing is at most 2. Here, disproving a conjec
ture of R. Yuster, we show that for any fixed, positive $alpha$ there are arbitrarily large graphs $G$ of positive density satisfying $tau_3(G)>(1-o(1))|G|/2$ and $ u_3(G)<(1+alpha)|G|/4$.
