Chaya Keller

activity

20092026

most citedOn Convex Geometric Graphs with no

k + 1

Pairwise Disjoint Edges

1 citations · 1 across the 24 of their papers we have counts for

collaborators

33 papers

math.CO2026

New Quantitative Bounds for the $(p, q)$ -Theorem for Unions of Convex Sets

Chaya Keller, Shakhar Smorodinsky

A set in $R^{d}$ is $s$ -convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p, q)$ property if among any $p$ sets in $F$ , some $q$ intersect. L…

math.CO2026

A Colorful Extension of VC-dimension and Geometric Applications

Chaya Keller, Shakhar Smorodinsky

The VC-dimension is a fundamental measure of the complexity of a set system. In this paper, we introduce and study a colorful variant of VC-dimension that captures the behavior of…

math.CO2026

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

Chaya Keller, Micha A. Perles

The convexity number of a set $X \subset R^{2}$ is the minimum number of convex subsets required to cover it. We study the following question: what is the largest possible c…

math.CO2025

Complements of finite unions of convex sets

Chaya Keller, Micha A. Perles

Finite unions of convex sets are a central object of study in discrete and computational geometry. In this paper we initiate a systematic study of complements of such unions -- i.e…

math.CO2025

On saturated triangulation-free convex geometric graphs

David Garber, Chaya Keller, Olga Nissenbaum +1

A convex geometric graph is a graph whose vertices are the corners of a convex polygon P in the plane and whose edges are boundary edges and diagonals of the polygon. It is called…

math.CO2025

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

Chaya Keller, Shakhar Smorodinsky

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 v…

math.CO2024

On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects

Timothy M. Chan, Chaya Keller, Shakhar Smorodinsky

The hypergraph Zarankiewicz's problem, introduced by Erdős in 1964, asks for the maximum number of hyperedges in an $r$ -partite hypergraph with $n$ vertices in each part that does…

math.CO2023

Zarankiewicz's problem via $ε$ -t-nets

Chaya Keller, Shakhar Smorodinsky

The classical Zarankiewicz's problem asks for the maximum number of edges in a bipartite graph on $n$ vertices which does not contain the complete bipartite graph $K_{t, t}$ . In one…

math.CO2023

An $(ℵ_{0}, k + 2)$ -Theorem for $k$ -Transversals

Chaya Keller, Micha A. Perles

A family $F$ of sets satisfies the $(p, q)$ -property if among every $p$ members of $F$ , some $q$ can be pierced by a single point. The celebrated $(p, q)$ -theorem…

math.CO2022

Conflict-Free Colouring of Subsets

Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky +1

We introduce and study conflict-free colourings of $t$ -subsets in hypergraphs. In such colourings, one assigns colours to all subsets of vertices of cardinality $t$ such that in an…

math.CO2021

A solution to Ringel's circle problem

James Davies, Chaya Keller, Linda Kleist +2

We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to Ringel's…

math.CO2021

On Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs

Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky +1

For $n \geq s > r \geq 1$ and $k \geq 2$ , write $n \to (s)_{k}^{r}$ if every hyperedge colouring with $k$ colours of the complete $r$ -uniform hypergraph on $n$ vertices has a mon…

math.CO2021

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

Chaya Keller, Balázs Keszegh, Dömötör Pálvölgyi

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.…

math.CO2020

No Krasnoselskii number for general sets in $R^{2}$

Chaya Keller, Micha A. Perles

For a family $F$ of sets in $R^{d}$ , the Krasnoselskii number of $F$ is the smallest $m$ such that for any $S \in F$ , if every $m$ points of $S…

cs.CG2020

Error Resilient Space Partitioning

Orr Dunkelman, Zeev Geyzel, Chaya Keller +4

A major research area in discrete geometry is to consider the best way to partition the $d$ -dimensional Euclidean space $R^{d}$ under various quality criteria. In this paper…

cs.DM2020

The $ε$ - $t$ -Net Problem

Noga Alon, Bruno Jartoux, Chaya Keller +2

We study a natural generalization of the classical $ε$ -net problem (Haussler--Welzl 1987), which we call the " $ε$ - $t$ -net problem": Given a hypergraph on $n$ vertices and parameter…

math.CO2019

On sets of $n$ points in general position that determine lines that can be pierced by $n$ points

Chaya Keller, Rom Pinchasi

Let $P$ be a set of $n$ points in general position in the plane. Let $R$ be a set of $n$ points disjoint from $P$ such that for every $x, y \in P$ the line through $x$ and $y$ conta…

math.CO2018

A new lower bound on Hadwiger-Debrunner numbers in the plane

Chaya Keller, Shakhar Smorodinsky

A family of sets $F$ is said to satisfy the $(p, q)$ property if among any $p$ sets in $F$ , some $q$ have a non-empty intersection. Hadwiger and Debrunner (1957) conjectured that fo…

math.CO2018

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

Chaya Keller, Micha A. Perles

Let G be a complete convex geometric graph, and let F be a family of subgraphs of G. A blocker for F is a set of edges, of smallest possible size, that has an edge in common with e…

math.CO2017

Reconstruction of the Path Graph

Chaya Keller, Yael Stein

Let $P$ be a set of $n \geq 5$ points in convex position in the plane. The path graph $G (P)$ of $P$ is an abstract graph whose vertices are non-crossing spanning paths of $P$ , such…

math.CO2017

Blockers for Triangulations of a Convex Polygon and a Geometric Maker-Breaker Game

Chaya Keller, Yael Stein

Let $G$ be a complete convex geometric graph whose vertex set $P$ forms a convex polygon $C$ , and let $F$ be a family of subgraphs of $G$ . A blocker for $F$ is a set of edges, of s…

math.CO2017

From a $(p, 2)$ -Theorem to a Tight $(p, q)$ -Theorem

Chaya Keller, Shakhar Smorodinsky

A family $F$ of sets is said to satisfy the $(p, q)$ -property if among any $p$ sets of $F$ some $q$ intersect. The celebrated $(p, q)$ -theorem of Alon and Kleitman asserts that any f…

math.CO2017

Conflict-Free Coloring of String Graphs

Chaya Keller, Alexandre Rok, Shakhar Smorodinsky

Conflict-free coloring (in short, CF-coloring) of a graph $G = (V, E)$ is a coloring of $V$ such that the neighborhood of each vertex contains a vertex whose color differs from the…

math.CO2017

Conflict-Free Coloring of Intersection Graphs of Geometric Objects

Chaya Keller, Shakhar Smorodinsky

In FOCS'2002, Even et al. introduced and studied the notion of conflict-free colorings of geometrically defined hypergraphs. They motivated it by frequency assignment problems in c…

New Quantitative Bounds for the (p,q)-Theorem for Unions of Convex Sets

A Colorful Extension of VC-dimension and Geometric Applications

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

Complements of finite unions of convex sets

On saturated triangulation-free convex geometric graphs

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

On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects

Zarankiewicz's problem via ε-t-nets

An (ℵ0​,k+2)-Theorem for k-Transversals

Conflict-Free Colouring of Subsets

A solution to Ringel's circle problem

On Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs

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

No Krasnoselskii number for general sets in R2

Error Resilient Space Partitioning

The ε-t-Net Problem

On sets of n points in general position that determine lines that can be pierced by n points

A new lower bound on Hadwiger-Debrunner numbers in the plane

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

Reconstruction of the Path Graph

Blockers for Triangulations of a Convex Polygon and a Geometric Maker-Breaker Game

From a (p,2)-Theorem to a Tight (p,q)-Theorem

Conflict-Free Coloring of String Graphs

Conflict-Free Coloring of Intersection Graphs of Geometric Objects

New Quantitative Bounds for the $(p, q)$ -Theorem for Unions of Convex Sets

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

Zarankiewicz's problem via $ε$ -t-nets

An $(ℵ_{0}, k + 2)$ -Theorem for $k$ -Transversals

No Krasnoselskii number for general sets in $R^{2}$

The $ε$ - $t$ -Net Problem

On sets of $n$ points in general position that determine lines that can be pierced by $n$ points

From a $(p, 2)$ -Theorem to a Tight $(p, q)$ -Theorem