6 papers · 1 filter
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…
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…
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…
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…
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…
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 vertices which does not contain the complete bipartite graph . In one…