CaltechAUTHORS
  A Caltech Library Service

Minimal definable graphs of definable chromatic number at least three

Carroy, Raphaël and Miller, Benjamin D. and Schrittesser, David and Vidnyánszky, Zoltán (2021) Minimal definable graphs of definable chromatic number at least three. Forum of Mathematics, Sigma, 9 . Art. No. E7. ISSN 2050-5094. https://resolver.caltech.edu/CaltechAUTHORS:20210304-150950107

[img]
Preview
PDF - Published Version
Creative Commons Attribution.

456Kb
[img] PDF - Submitted Version
See Usage Policy.

310Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210304-150950107

Abstract

We show that there is a Borel graph on a standard Borel space of Borel chromatic number three that admits a Borel homomorphism to every analytic graph on a standard Borel space of Borel chromatic number at least three. Moreover, we characterize the Borel graphs on standard Borel spaces of vertex-degree at most two with this property and show that the analogous result for digraphs fails.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1017/fms.2020.58DOIArticle
https://arxiv.org/abs/1906.08373arXivDiscussion Paper
Additional Information:© The Author(s), 2021. Published by Cambridge University Press. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited. Received: 26 November 2019; Revised: 14 September 2020; Accepted: 5 October 2020. The authors were supported in part by FWF Grants P28153 and P29999. R. Carroy was supported by PRIN grant number 2017NWTM8R. Z. Vidnyánszky was also supported by NKFIH, grant nos. 113047 and 129211 and FWF Grant M2779. Conflict of Interest: None.
Funders:
Funding AgencyGrant Number
Fonds Zur Förderung der Wissenschaftlichen Forschung (FWF)P28153
Fonds Zur Förderung der Wissenschaftlichen Forschung (FWF)P29999
Ministero dell'Università e della Ricerca (MIUR)2017NWTM8R
National Research, Development and Innovation Fund (NKFIA)113047
National Research, Development and Innovation Fund (NKFIA)129211
Fonds Zur Förderung der Wissenschaftlichen Forschung (FWF)M2779
National Research, Development and Innovation Office (Hungary)UNSPECIFIED
Subject Keywords:Borel bipartite; Borel coloring
Classification Code:2020 Mathematics Subject Classification: Primary: 03E15, 28A05
Record Number:CaltechAUTHORS:20210304-150950107
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210304-150950107
Official Citation:Carroy, R., Miller, B., Schrittesser, D., & Vidnyánszky, Z. (2021). Minimal definable graphs of definable chromatic number at least three. Forum of Mathematics, Sigma, 9, E7. doi:10.1017/fms.2020.58
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108314
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:04 Mar 2021 23:24
Last Modified:04 Mar 2021 23:24

Repository Staff Only: item control page