Source author record

Shira Zerbib

Shira Zerbib appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics

Catalog footprint

What is connected

6works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Fractionally balanced hypergraphs and rainbow KKM theorems

A d-partite hypergraph is called *fractionally balanced* if there exists a non-negative, not identically zero, function on its edge set that has constant degrees in each vertex side. Using a topological version of Hall's theorem we prove lower bounds on the matching number of such hypergraphs. These bounds yield rainbow versions of the KKM theorem for products of simplices, which in turn are used to obtain some results on multiple-cake division, and on rainbow matchings in families of d-intervals.

preprint2020arXiv

Large triangle packings and Tuza's conjecture in sparse random graphs

The triangle packing number $ν(G)$ of a graph $G$ is the maximum size of a set of edge-disjoint triangles in $G$. Tuza conjectured that in any graph $G$ there exists a set of at most $2ν(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random graph $G=G(n,m)$, when $m \le 0.2403n^{3/2}$ or $m\ge 2.1243n^{3/2}$. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs.

preprint2016arXiv

Edge-covers in d-interval hypergraphs

A d-interval hypergraph has d disjoint copies of the unit interval as its vertex set, and each edge is the union of d subintervals, one on each copy. Extending a classical result of Gallai on the case d = 1, Tardos and Kaiser used topological tools to bound the ratio between the transversal number and the matching number in such hypergraphs. We take a dual point of view, and bound the edge-covering number (namely the minimal number of edges covering the entire vertex set) in terms of a parameter expressing independence of systems of partitions of the d unit intervals. The main tool we use is an extension of the KKM theorem to products of simplices, due to Peleg. Our approach also yields a new proof of the Tardos-Kaiser result.

preprint2016arXiv

On the zone complexity of a vertex

Let $L$ be a set of $n$ lines in the real projective plane in general position. We show that there exists a vertex $v\in \A(L)$ such that $v$ is positioned in a face of size at most 5 in the arrangement obtained by removing the two lines passing through $v$.

preprint2014arXiv

Fractional covers and matchings in families of weighted $d$-intervals

A $d$-{\em interval} is a union of at most $d$ disjoint closed intervals on a fixed line. Tardos [Combinatorica 15 (1995), 123-134] and the second author [Disc. Comput. Geom. 18 (1997), 195-203] used topological tools to bound the transversal number $τ$ of a family $H$ of $d$-intervals in terms of $d$ and the matching number $ν$ of $H$. We investigate the weighted and fractional versions of this problem and prove upper bounds that are tight up to constant factors. We apply both the topological method and an approach of Alon [Disc. Comput. Geom. 19 (1998), 333-334]. For the use of the latter, we prove a weighted version of Turán's theorem. We also provide a proof of the second author's upper bound that is more direct than the original proof.

preprint2013arXiv

The number of distinct distances from a vertex of a convex polygon

Erdős conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least floor(n/2) distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 - O(1). In the present note, we slightly improve on this result to (13/36 + eps)n - O(1) for eps ~= 1/23000. Our main ingredient is an improved bound on the maximum number of isosceles triangles determined by P.