Source author record

Yuri Rabinovich

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms math.MG Discrete Mathematics math.AT

Catalog footprint

Research overview

7works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2017arXiv

Rational Polygons: Odd Compression Ratio and Odd Plane Coverings

Let P be a polygon with rational vertices in the plane. We show that for any finite odd-sized collection of translates of P, the area of the set of points lying in an odd number of these translates is bounded away from 0 by a constant depending on P alone. The key ingredient of the proof is a construction of an odd cover of the plane by translates of P. That is, we establish a family F of translates of P covering (almost) every point in the plane a uniformly bounded odd number of times.

preprint2015arXiv

Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes

A $d$ -hypertree on $[n]$ is a maximal acyclic $d$ -dimensional simplicial complex with full $(d-1)$ -skeleton on the vertex set $[n]$ . Alternatively, in the language of algebraic topology, it is a minimal $d$ -dimensional simplicial complex $T$ (assuming full $(d-1)$ -skeleton) such that $\tilde{H}_{d-1}(T;\mathbb{F})=0$ . The $d$ -hypertrees are a basic object in combinatorial theory of simplicial complexes. They have been studied; and yet, many of their structural aspects remain poorly understood. In this paper we study the boundaries $\partial_d T$ of $d$ -hypertrees, and the fundamental $d$ -cycles defined by them. Our findings include: 1. A full characterization of $\partial_d T$ over $\mathbb{F}_2$ for $d \leq 2$ , and some partial results for $d \geq 3$ . 2. Lower bounds on the maximum size of a largest simple $d$ -cycle on $[n]$ . In particular, for $d=2$ , we construct a {\em Hamiltonian $d$ -cycle} $H$ on $[n]$ , i.e., a simple $d$ -cycle of size ${{n-1} \choose d} + 1$ . For $d\geq 3$ , we construct a simple $d$ -cycle of size ${{n-1} \choose d} - O(n^{d-2})$ . 3. Observing that the maximum of the expected distance between two vertices chosen uniformly at random in a tree ( $1$ -hypertree) on $[n]$ is at most $\thicksim n/3$ , attained on Hamiltonian paths, we ask a similar question about $d$ -hypertrees. "How large can be the {\em average} size of a fundamental cycle of a $d$ -hypertree $T$ (i.e., the expected size of the dependency created by adding a $d$ -simplex on $[n]$ , chosen uniformly at random, to $T$ )?" For every $d \in \mathbb{N}$ , we construct an infinite family of $d$ -hypertrees $\{T\}$ with the average size of a fundamental cycle at least $c_d\, |T| \,=\, c_d\,{n-1 \choose d}$ , where $c_d$ is a constant depending on the dimension $d$ alone.

preprint2015arXiv

Extremal problems on shadows and hypercuts in simplicial complexes

Let $F$ be an $n$ -vertex forest. We say that an edge $e\notin F$ is in the shadow of $F$ if $F\cup\{e\}$ contains a cycle. It is easy to see that if $F$ is "almost a tree", that is, it has $n-2$ edges, then at least $\lfloor\frac{n^2}{4}\rfloor$ edges are in its shadow and this is tight. Equivalently, the largest number of edges an $n$ -vertex cut can have is $\lfloor\frac{n^2}{4}\rfloor$ . These notions have natural analogs in higher $d$ -dimensional simplicial complexes, graphs being the case $d=1$ . The results in dimension $d>1$ turn out to be remarkably different from the case in graphs. In particular the corresponding bounds depend on the underlying field of coefficients. We find the (tight) analogous theorems for $d=2$ . We construct $2$ -dimensional " $\mathbb Q$ -almost-hypertrees" (defined below) with an empty shadow. We also show that the shadow of an " $\mathbb F_2$ -almost-hypertree" cannot be empty, and its least possible density is $Θ(\frac{1}{n})$ . In addition we construct very large hyperforests with a shadow that is empty over every field. For $d\ge 4$ even, we construct $d$ -dimensional $\mathbb{F} _2$ -almost-hypertree whose shadow has density $o_n(1)$ . Finally, we mention several intriguing open questions.

preprint2015arXiv

On Connectivity of the Facet Graphs of Simplicial Complexes

The paper studies the connectivity properties of facet graphs of simplicial complexes of combinatorial interest. In particular, it is shown that the facet graphs of $d$ -cycles, $d$ -hypertrees and $d$ -hypercuts are, respectively, $(d+1)$ , $d$ , and $(n-d-1)$ -vertex-connected. It is also shown that the facet graph of a $d$ -cycle cannot be split into more than $s$ connected components by removing at most $s$ vertices. In addition, the paper discusses various related issues, as well as an extension to cell-complexes.

preprint2014arXiv

Binary Jumbled Pattern Matching via All-Pairs Shortest Paths

In binary jumbled pattern matching we wish to preprocess a binary string $S$ in order to answer queries $(i,j)$ which ask for a substring of $S$ that is of size $i$ and has exactly $j$ 1-bits. The problem naturally generalizes to node-labeled trees and graphs by replacing "substring" with "connected subgraph". In this paper, we give an ${n^2}/{2^{Ω(\log n/\log \log n)^{1/2}}}$ time solution for both strings and trees. This odd-looking time complexity improves the state of the art $O(n^2/\log^2 n)$ solutions by more than any poly-logarithmic factor. It originates from the recent seminal algorithm of Williams for min-plus matrix multiplication. We obtain the result by giving a black box reduction from trees to strings. This is then combined with a reduction from strings to min-plus matrix multiplications.

preprint2010arXiv

Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs

In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of Bǎdoiu, Indyk, and Sidiropoulos (2007) and Bǎdoiu, Demaine, Hajiaghayi, Sidiropoulos, and Zadimoghaddam (2008)). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of metric relaxed minor and show that if G contains an alpha-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is at meast alpha. Then, for H=K_{2,3}, we present an algorithm which either finds an alpha-relaxed minor, or produces an O(alpha)-embedding into an outerplanar metric.

preprint2010arXiv

Finite Volume Spaces and Sparsification

We introduce and study finite $d$ -volumes - the high dimensional generalization of finite metric spaces. Having developed a suitable combinatorial machinery, we define $\ell_1$ -volumes and show that they contain Euclidean volumes and hypertree volumes. We show that they can approximate any $d$ -volume with $O(n^d)$ multiplicative distortion. On the other hand, contrary to Bourgain's theorem for $d=1$ , there exists a $2$ -volume that on $n$ vertices that cannot be approximated by any $\ell_1$ -volume with distortion smaller than $\tildeΩ(n^{1/5})$ . We further address the problem of $\ell_1$ -dimension reduction in the context of $\ell_1$ volumes, and show that this phenomenon does occur, although not to the same striking degree as it does for Euclidean metrics and volumes. In particular, we show that any $\ell_1$ metric on $n$ points can be $(1+ ε)$ -approximated by a sum of $O(n/ε^2)$ cut metrics, improving over the best previously known bound of $O(n \log n)$ due to Schechtman. In order to deal with dimension reduction, we extend the techniques and ideas introduced by Karger and Bencz{ú}r, and Spielman et al.~in the context of graph Sparsification, and develop general methods with a wide range of applications.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Yuri Rabinovich

Research overview

Is this your work?

7 publications

Rational Polygons: Odd Compression Ratio and Odd Plane Coverings

Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes

Extremal problems on shadows and hypercuts in simplicial complexes

On Connectivity of the Facet Graphs of Simplicial Complexes

Binary Jumbled Pattern Matching via All-Pairs Shortest Paths

Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs

Finite Volume Spaces and Sparsification

See the researcher in context

Building this map preview