53 citations · 92 across the 32 of their papers we have counts for
8 papers · 1 filter
From a -Theorem to a Tight -Theorem
Chaya Keller, Shakhar Smorodinsky
A family of sets is said to satisfy the -property if among any sets of some intersect. The celebrated -theorem of Alon and Kleitman asserts that any f…
Conflict-Free Coloring of String Graphs
Chaya Keller, Alexandre Rok, Shakhar Smorodinsky
Conflict-free coloring (in short, CF-coloring) of a graph is a coloring of such that the neighborhood of each vertex contains a vertex whose color differs from the…
Balanced Line Separators of Unit Disk Graphs
Paz Carmi, Man Kwun Chiu, Matthew J. Katz +6
We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of unit disks in the plane there exists a line such that $\…
Hypergraphical Clustering Games of Mis-Coordination
Rann Smorodinsky, Shakhar Smorodinsky
We introduce and motivate the study of hypergraphical clustering games of mis-coordination. For two specific variants we prove the existence of a pure Nash equilibrium and provide…
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…
On Piercing Numbers of Families Satisfying the Property
Chaya Keller, Shakhar Smorodinsky
The Hadwiger-Debrunner number is the minimal size of a piercing set that can always be guaranteed for a family of compact convex sets in that satisfies t…
On the union complexity of families of axis-parallel rectangles with a low packing number
Chaya Keller, Shakhar Smorodinsky
Let R be a family of n axis-parallel rectangles with packing number p-1, meaning that among any p of the rectangles, there are two with a non-empty intersection. We show that the u…
Bounding a global red-blue proportion using local conditions
Márton Naszódi, Leonardo Martínez-Sandoval, Shakhar Smorodinsky
We study the following local-to-global phenomenon: Let and be two finite sets of (blue and red) points in the Euclidean plane . Suppose that in each "neighbor…