3 papers
math.CO2026
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…
cs.DM2025
Induced matching treewidth and tree-independence number, revisited
Noga Alon, Martin MilaniÄ, PaweÅ RzÄ Å¼ewski
We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with…
cs.DS2024
A Bicriterion Concentration Inequality and Prophet Inequalities for -Fold Matroid Unions
Noga Alon, Nick Gravin, Tristan Pollner +4
We investigate prophet inequalities with competitive ratios approaching , seeking to generalize -uniform matroids. We first show that large girth does not suffice: for all $k…