Computable vs descriptive combinatorics of local problems on trees

DOI10.1017/JSL.2023.47MaRDI QIDQ7033943zbMATH OpenFDO

Authors Felix Weilacher

Publication date 3 February 2025

Published in The Journal of Symbolic Logic (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/JSL.2023.47

zbMATH Keywords

Baire measurabilitycomputabilitycontinuitygraph coloring

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites work

• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
• Effective coloration
• Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)
• scientific article; zbMATH DE number 7829261 (Why is no real title available?)
• Locality in Distributed Graph Algorithms
• Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
• The Effective Version of Brooks' Theorem

Cited in

(2)

• Borel versions of the local lemma and local algorithms for graphs of finite asymptotic separation index
• Borel local lemma: arbitrary random variables and limited exponential growth

This page was built for publication: Computable vs descriptive combinatorics of local problems on trees

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