53 citations · 54 across the 12 of their papers we have counts for
13 papers · 1 filter
New Quantitative Bounds for the -Theorem for Unions of Convex Sets
Chaya Keller, Shakhar Smorodinsky
A set in is -convex if it is the union of at most convex sets. A family satisfies the property if among any sets in , some intersect. L…
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…
New Sufficient Conditions for Linear-Sized Epsilon-Nets and -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 -theorem bounds from above the minimum size of a v…
Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets
Noga Alon, Shakhar Smorodinsky
We prove a new Radon type theorem for unions of convex sets, settling an open problem posed by Kalai in the 1970s. We also define and study an extension of the notion of the VC-dim…
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 -partite hypergraph with vertices in each part that does…
On conflict-free colorings of cyclic polytopes and the girth conjecture for graphs
Seunghun Lee, Shakhar Smorodinsky
We study the conflict-free chromatic number of hypergraphs derived from the family of facets of -dimensional cyclic polytopes with vertices. While in odd dimensions the…