On Homomorphism Graphs

DOI10.1017/FMP.2024.8MaRDI QIDQ6382336zbMATH OpenOpenAlexFDO

Authors Sebastian F. Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, Zoltán Vidnyánszky

Publication date 5 November 2021

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/fmp.2024.8

Mathematics Subject Classification ID

Descriptive set theory (03E15) Coloring of graphs and hypergraphs (05C15) Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05)

Abstract: We introduce a new type 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. The motivation for the construction comes from the adaptation of this method to the LOCAL model of distributed computing. Our approach unifies the previous results in the area, as well as produces new ones. In particular, we show that for $Delta>2$ it is impossible to give a simple characterization of acyclic $Delta$-regular Borel graphs with Borel chromatic number at most $Delta$: such graphs form a $mathbf{Sigma}_2^1$-complete set. This implies a strong failure of Brooks'-like theorems in the Borel context.

Cited in

(6)

• Creating a network-state homomorphism through optimization
• Complexity of finite Borel asymptotic dimension
• Complexity of codes for Ramsey positive sets
• Measurable Vizing's theorem
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)

This page was built for publication: On Homomorphism Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6382336)