Alladi Ramakrishnan Hall

Packing, combinatorial Macbeath regions and semi-algebraic set systems

Arijit Ghosh

ISI Kolkata

The packing lemma of Haussler (J. of Comb. Theory, Ser. A, 1995) states that given a set system with bounded VC dimension, if every pair of sets in the set system have large symmetric difference, then the set system cannot contain too many sets. This has turned out to be the technical foundation for many results in combinatorial geometry and discrepancy. Recently it was generalized by Dutta et al. (Disc. & Compt. Geom., 2016) and Mustafa (Disc. & Compt. Geom., 2016) to the shallow packing lemma, applying to set systems as a function of their shallow-cell complexity. We proved the following new results related to packings:

-- An optimal lower bound for shallow packings, thus settling the open question in Ezra (SIAM J. on Computing, 2016) and Dutta et al. (Disc. & Comput. Geom., 2016).

-- Improved bounds on combinatorial Macbeath regions, or Mnets, providing a combinatorial analogue to Macbeath regions in convex geometry (Ann. of Math., 1952). This resolves the main open problem in Mustafa and Ray (Disc & Comput. Geom., 2016).

-- Mnets provide a general, more powerful framework from which the state-of-the-art unweighted Epsilon-net results of Varadarajan (STOC, 2010) and Chan et al. (SODA, 2012) follow immediately.

-- Our upper bounds on Mnets for general semialgebraic set systems are asymptotically tight. We also give a more precise lower bound in terms of shallow-cell complexity.

-- Simplifying and generalizing one of the main technical tools in Fox et al. (J. of the Euro. Math. Soc., to appear). Besides using the packing lemma and a combinatorial construction, our proofs combine tools from polynomial partitioning of Guth and Katz (Ann. of Math., 2014) and the probabilistic method.