Source author record

Chaya Keller

Chaya Keller 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

Catalog footprint

What is connected

9works

2topics

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.

preprint2026arXiv

New Sufficient Conditions for Linear-Sized Epsilon-Nets and $(p,2)$-Theorems

An $ε$-net theorem for a hypergraph upper bounds the minimum size of a vertex set that pierces all $ε$-heavy hyperedges. A $(p,2)$-theorem bounds from above the minimum size of a vertex set that pierces all hyperedges, in terms of the maximum size of a set of pairwise disjoint hyperedges. Numerous works studied $ε$-net theorems and $(p,2)$-theorems that guarantee the existence of small-sized piercing sets. We focus on the question: In which settings the asymptotically smallest possible piercing sets -- i.e., $ε$-nets of size $O(\frac{1}ε)$ and piercing sets of size $O(p)$ in $(p,2)$-theorems, are guaranteed? We obtain several sufficient criteria for the existence of such linear $ε$-net theorems and $(p,2)$-theorems that unveil interesting connections to graph theory and improve and generalize several previous results. Most notably, we exhibit an unexpected relation of $ε$-nets to the classical Zarankiewicz's problem in graph theory. We show that a linear bound in the Zarankiewicz-type problem that asks for the maximum size of a bipartite graph with no copy of $K_{2,t}$, implies a linear $ε$-net theorem for the corresponding neighborhood hypergraph. We also show that hypergraphs with a hereditarily linear-sized Delaunay graph admit an almost linear $(p,2)$-theorem, and deduce that incidence hypergraphs of non-piercing regions in the plane admit a linear $(p,2)$-theorem, significantly improving previous results on such hypergraphs. Our work presents a landscape of sufficient conditions for the existence of linear $ε$-net theorems and $(p,2)$-theorems, with complex interrelations between them. Many of the interrelations are still unknown and call for future research.

preprint2026arXiv

On the Largest Convexity Number of Co-Finite Sets in the Plane

The convexity number of a set $X \subset \mathbb{R}^2$ is the minimum number of convex subsets required to cover it. We study the following question: what is the largest possible convexity number $f(n)$ of $\mathbb{R}^2 \setminus S$, where $S$ is a set of $n$ points in general position in the plane? We prove that for all $n \geq 4$, $\lfloor\frac{n+5}{2}\rfloor \leq f(n) \leq \frac{7n+44}{11}$. We also show that for every $n \geq 4$, if the points of $S$ are in convex position then the convexity number of $\mathbb{R}^2 \setminus S$ is $\lfloor\frac{n+5}{2}\rfloor$. This solves a problem of Lawrence and Morris [Finite sets as complements of finite unions of convex sets, Disc. Comput. Geom. 42 (2009), 206-218].

preprint2022arXiv

On the number of hyperedges in the hypergraph of lines and pseudo-discs

Consider the hypergraph whose vertex set is a family of $n$ lines in general position in the plane, and whose hyperedges are induced by intersections with a family of pseudo-discs. We prove that the number of $t$-hyperedges is bounded by $O_t(n^2)$ and that the total number of hyperedges is bounded by $O(n^3)$. Both bounds are tight.

preprint2016arXiv

Blockers for simple Hamiltonian paths in convex geometric graphs of even order

Let G be a complete convex geometric graph on 2m vertices, and let F be a family of subgraphs of G. A blocker for F is a set of edges, of smallest possible size, that meets every element of F. In [C. Keller and M. A. Perles, On the smallest sets blocking simple perfect matchings in a convex geometric graph, Israel J. Math. 187 (2012), pp. 465-484], we gave an explicit description of all blockers for the family of simple perfect matchings (SPMs) of G. In this paper we show that the family of simple Hamiltonian paths (SHPs) in G has exactly the same blockers as the family of SPMs. Our argument is rather short, and provides a much simpler proof of the result of [KP12].

preprint2016arXiv

Improved bounds on the Hadwiger-Debrunner numbers

Let $HD_d(p,q)$ denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in $\mathbb{R}^d$ which satisfy the $(p,q)$-property ($p \geq q \geq d+1$). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that $HD_d(p,q)$ exists for all $p \geq q \geq d+1$. Specifically, they prove that $HD_d(p,d+1)$ is $\tilde{O}(p^{d^2+d})$. We present several improved bounds: (i) For any $q \geq d+1$, $HD_d(p,q) = \tilde{O}(p^{d \left(\frac{q-1}{q-d}\right)})$. (ii) For $q \geq \log p$, $HD_d(p,q) = \tilde{O}(p+(p/q)^d)$. (iii) For every $ε> 0$ there exists a $p_0 = p_0(ε)$ such that for every $p \geq p_0$ and for every $q \geq p^{\frac{d-1}{d}+ε}$ we have: $p-q+1 \leq HD_d(p,q) \leq p-q+2$. The latter is the first near tight estimate of $HD_d(p,q)$ for an extended range of values of $(p,q)$ since the 1957 Hadwiger-Debrunner theorem. We also prove a $(p,2)$-theorem for families in $\mathbb{R}^2$ with union complexity below a specific quadratic bound. Based on this, we introduce a polynomial time constant factor approximation algorithm for MAX-CLIQUE of intersection graphs of convex sets satisfying this property.

preprint2015arXiv

On Convex Geometric Graphs with no $k+1$ Pairwise Disjoint Edges

A well-known result of Kupitz from 1982 asserts that the maximal number of edges in a convex geometric graph (CGG) on $n$ vertices that does not contain $k+1$ pairwise disjoint edges is $kn$ (provided $n>2k$). For $k=1$ and $k=n/2-1$, the extremal examples are completely characterized. For all other values of $k$, the structure of the extremal examples is far from known: their total number is unknown, and only a few classes of examples were presented, that are almost symmetric, consisting roughly of the $kn$ "longest possible" edges of $CK(n)$, the complete CGG of order $n$. In order to understand further the structure of the extremal examples, we present a class of extremal examples that lie at the other end of the spectrum. Namely, we break the symmetry by requiring that, in addition, the graph admit an independent set that consists of $q$ consecutive vertices on the boundary of the convex hull. We show that such graphs exist as long as $q \leq n-2k$ and that this value of $q$ is optimal. We generalize our discussion to the following question: what is the maximal possible number $f(n,k,q)$ of edges in a CGG on $n$ vertices that does not contain $k+1$ pairwise disjoint edges, and, in addition, admits an independent set that consists of $q$ consecutive vertices on the boundary of the convex hull? We provide a complete answer to this question, determining $f(n,k,q)$ for all relevant values of $n,k$ and $q$.

preprint2014arXiv

Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph

Let P be a finite set of points in general position in the plane. The structure of the complete graph K(P) as a geometric graph includes, for any pair [a,b],[c,d] of vertex-disjoint edges, the information whether they cross or not. The simple (i.e., non-crossing) spanning trees (SSTs) of K(P) are the vertices of the so-called Geometric Tree Graph of P, G(P). Two such vertices are adjacent in G(P) if they differ in exactly two edges, i.e., if one can be obtained from the other by deleting an edge and adding another edge. In this paper we show how to reconstruct from G(P) (regarded as an abstract graph) the structure of K(P) as a geometric graph. We first identify within G(P) the vertices that correspond to spanning stars. Then we regard each star S(z) with center z as the representative in G(P) of the vertex z of K(P). (This correspondence is determined only up to an automorphism of K(P) as a geometric graph.) Finally we determine for any four distinct stars S(a), S(b), S(c), and S(d), by looking at their relative positions in G(P), whether the corresponding segments cross.

preprint2012arXiv

Blockers for non-crossing spanning trees in complete geometric graphs

In this paper we present a complete characterization of the smallest sets that block all the simple spanning trees (SSTs) in a complete geometric graph. We also show that if a subgraph is a blocker for all SSTs of diameter at most 4, then it must block all simple spanning subgraphs, and in particular, all SSTs. For convex geometric graphs, we obtain an even stronger result: being a blocker for all SSTs of diameter at most 3 is already sufficient for blocking all simple spanning subgraphs.

preprint2010arXiv

Characterization of co-blockers for simple perfect matchings in a convex geometric graph

Consider the complete convex geometric graph on $2m$ vertices, $CGG(2m)$, i.e., the set of all boundary edges and diagonals of a planar convex $2m$-gon $P$. In [C. Keller and M. Perles, On the Smallest Sets Blocking Simple Perfect Matchings in a Convex Geometric Graph], the smallest sets of edges that meet all the simple perfect matchings (SPMs) in $CGG(2m)$ (called "blockers") are characterized, and it is shown that all these sets are caterpillar graphs with a special structure, and that their total number is $m \cdot 2^{m-1}$. In this paper we characterize the co-blockers for SPMs in $CGG(2m)$, that is, the smallest sets of edges that meet all the blockers. We show that the co-blockers are exactly those perfect matchings $M$ in $CGG(2m)$ where all edges are of odd order, and two edges of $M$ that emanate from two adjacent vertices of $P$ never cross. In particular, while the number of SPMs and the number of blockers grow exponentially with $m$, the number of co-blockers grows super-exponentially.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint