Skip to content
Main menu hidden.

Conflict-Free Colouring of Subsets

Time Friday 25 November, 2022 at 14:15 - 15:15
Place Zoom

Abstract: A conflict-free colourings of t-subsets in hypergraphs is a colouring where one assigns colours to all subsets of vertices of cardinality t such that in any hyperedge of cardinality at least t there is a uniquely coloured t-subset. In the talk, I will present the following results. 

(i) For any fixed t, the t-subsets in any set P of n points in the plane can be coloured with O(t2  log2 n) colours so that any axis-parallel rectangle that contains at least t points of P also contains a uniquely coloured t-subset.

(ii) For a wide class of `well behaved' geometrically defined hypergraphs, there is a nearly tight upper bound on their t-subset conflict-free chromatic number.

This is a joint work with Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.  

Contact Victor Falgas Ravry to receive the Zoom link. 

Event type: Seminar

Speaker: Yelena Yuditsky, University Libre de Bruxelles

Victor Falgas Ravry
Read about Victor Falgas Ravry