Homepage of the Combinatorial Geometry Research Group

The COLORINGS IN COMBINATORIAL GEOMETRY project

We are supported from 2017-2022 by the Momentum (Lendület) program of the Hungarian Academy of Sciences (MTA). 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.

Results about polychromatic colorings of (primal) geometric hypergraphs

Summary of known results

Old page with results about cover-decomposition (dual) and citations: Table of most important results

Publications

Nothing yet...