CISPA
Browse
on-homomorphism-graphs.pdf (508.58 kB)

ON HOMOMORPHISM GRAPHS

Download (508.58 kB)
journal contribution
posted on 2024-05-24, 07:55 authored by Sebastian BrandtSebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, Zoltán Vidnyánszky
We introduce new types of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalization of the determinacy method of Marks [Mar16]. The motivation for the construction comes from the adaptation of this method to the LOCAL model of distributed computing [BCG+21]. Our approach unifies the previous results in the area, as well as produces new ones. In particular, strengthening the main result of [TV21], we show that for Δ>2, it is impossible to give a simple characterization of acyclic Δ-regular Borel graphs with Borel chromatic number at most Δ: such graphs form a Σ 1 2 -complete set. This implies a strong failure of Brooks-like theorems in the Borel context.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Journal

Forum of Mathematics, Pi

Volume

12

Page Range

e10-e10

Publisher

Cambridge University Press

Open Access Type

  • Gold

Sub Type

  • Article

BibTeX

@article{Brandt:Chang:Grebík:Grunau:Rozhoň:Vidnyánszky:2024, title = "ON HOMOMORPHISM GRAPHS", author = "Brandt, Sebastian" AND "Chang, Yi-Jun" AND "Grebík, Jan" AND "Grunau, Christoph" AND "Rozhoň, Václav" AND "Vidnyánszky, Zoltán", year = 2024, month = 5, journal = "Forum of Mathematics, Pi", pages = "e10--e10", publisher = "Cambridge University Press", issn = "2050-5086", doi = "10.1017/fmp.2024.8" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC