Homepage of the MTA-ELTE Lendület Combinatorial Geometry (CoGe) 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.

Publications

Balázs Keszegh, Coloring intersection hypergraphs of pseudo-disks, SoCG 2018, 52:1-52:15 [proceedings]

Dömötör Pálvölgyi, Weak embeddings of posets to the Boolean lattice, Discrete Mathematics and Theoretical Computer Science, 20(1):1-10, 2018 [journal]

Benjamin Gunby and Dömötör Pálvölgyi. Asymptotics of Pattern Avoidance in the Klazar Set Partition and Permutation-Tuple Settings [arxiv]

Dömötör Pálvölgyi. Complexity of Domination in Triangulated Plane Graphs [arxiv]

Zoltán Király and Dömötör Pálvölgyi. Acyclic orientations with degree constraints [arxiv]

Eyal Ackerman, Balázs Keszegh and Dömötör Pálvölgyi. Coloring Delaunay-Edges and their Generalizations [arxiv]

Balázs Keszegh and Dömötör Pálvölgyi. Plane drawings of the generalized Delaunay-graphs for pseudo-disks [arxiv]

Eyal Ackerman, Balázs Keszegh and Dömötör Pálvölgyi. Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs [arxiv]

Dömötör Pálvölgyi and Gábor Tardos. Unlabeled Compression Schemes Exceeding the VC-dimension. [arxiv]

Balázs Keszegh and Dömötör Pálvölgyi. An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes, Journal of Computational Geometry, 10(1):1-26, 2019 [journal]

Gábor Damásdi, Leonardo Martínez-Sandoval, Dániel T. Nagy, Zoltán Lóránt Nagy. Triangle areas determined by arrangements of planar lines. [arxiv]