Colorful Extensions of Infinite (p,q)-Theorems in Combinatorial Geometry

Speaker:

Arijit Ghosh

Organiser:

Arkadev Chattopadhyay

Date:

Tuesday, 27 Aug 2024, 16:00 to 17:00

Venue:

A-201 (STCS Seminar Room)

Category:

STCS Seminar

event.ics Print

Abstract

An infinite sequence of sets $\{B_n\}_{n\in\mathbb{N}}$ is said to be a heterochromatic sequence for an infinite collection $\left\{ \mathcal{F}_{n} \right\}_{n \in \mathbb{N}}$ of families of sets, if there exists a strictly increasing sequence of natural numbers $\left\{ i_{n}\right\}_{n \in \mathbb{N}}$ such that for all $n \in \mathbb{N}$ we have $B_{n} \in \mathcal{F}_{i_{n}}$ . In this talk, we will prove that if for each $n\in\mathbb{N}, \mathcal{F}_n$ is a family of nicely shaped convex sets in $\mathbb{R}^d$ such that each heterochromatic sequence $\{B_n\}_{n\in\mathbb{N}}$ of $\left\{ \mathcal{F}_{n} \right\}_{n \in \mathbb{N}}$ contains $k+2$ sets that can be pierced by a single $k$ -flat ( $k$ -dimensional affine space) then all but finitely many $\mathcal{F}_n$ 's can be pierced by finitely many $k$ -flats. This result generalizes the $(\aleph_0, k+2)$ -Theorem proved by Keller and Perles (SoCG'22) to the countably colorful setting. We have also established the tightness of our results by proving several no-go theorems.

This is a joint work with Sutanoya Chakraborty (PhD Student at ISI, Kolkata) and Soumi Nandi (PhD Student at ISI, Kolkata).

Short Bio:

Arijit Ghosh is currently an Associate Professor at ACM Unit, Indian Statistical Institute, Kolkata. He did his PhD in Computer Science from INRIA, France, and was a Postdoc at Max Planck Insitute for Informatics, Germany.