Combinatorial Geometry (CoGe) Research Group


Current members:

Péter Ágoston (PhD, 2019-)

Gábor Damásdi (PhD, 2018-)

Attila Jung (PhD, 2022-)

Balázs Keszegh

Márton Naszódi

Dömötör Pálvölgyi (head)

Visitors and past members:

Sameer Desai (Postdoc, 2020)

Narmada Varadarajan (MSc, 2019-2020)

Nóra Frankl (2018 Summer)

Tamás Hubai (Postdoc, 2017-2019)

Distinguished close collaborators:

Eyal Ackerman

János Pach

Géza Tóth


We are based at ELTE and the Alfréd Rényi Institute of Mathematics, Budapest. The goal of the project is to study a number of fundamental hypergraph coloring problems with special emphasis on their applications in discrete geometry and in the theory of packing and covering. Besides its theoretical interest and relationship to deep mathematical problems, this theory can be applied to practically any real world situation that involves partitioning given objects into groups with certain properties, such as scheduling.

For an illustration of a typical question, suppose that an area is covered by disks such that every point is contained in at least m disks, where m is a large integer. Is it possible to color the disks with two colors such that each of the color classes alone covers the whole area? We get different variants, if we consider other geometric families instead of disks, if we allow more colors to be used, or if we pose other requirements on the coloring. One of the goals of the COLORINGS IN COMBINATORIAL GEOMETRY project is to give necessary and sufficient conditions that geometric families need to satisfy to guarantee the existence of colorings of the above type. We outline a plan of abstraction, where geometric notions are replaced by purely combinatorial ones. This way we hope to identify and separate the conditions the underlying geometric objects need to possess in order to admit such colorings.

We were supported from 2017-2022 by the Momentum (Lendület) program of the Hungarian Academy of Sciences (MTA).