HEXAGONbeta

The random graph ideal and fractional coloring

A mix of human-written and AI-generated textHuman understanding: all partsmath.LO — Logicmath.CO — Combinatorics

Contributed by Carlos López-Callejas ↗

Version 1 / Oct 29, 2026 / CC BY 4.0

Abstract

The random graph ideal is pathological, answering a question of López-Abad et al. We prove this by constructing a positive hereditarily pathological restriction using Kneser graphs. We also prove that every FσF_\sigma ideal admitting a proper nonpathological FσF_\sigma extension has a least such extension. Moreover, for an FσF_\sigma ideal, being nonpathological, being an intersection of summable ideals, and being an intersection of matrix ideals are equivalent conditions. This answers both converses asked by Filipów and Tryba. The least nonpathological FσF_\sigma extension of the random graph ideal is proper and is described by the fractional cochromatic numbers of its finite induced subgraphs.

Provenance statement

The author had been working on this question since August 2025, looking for finite graphs on which one covering invariant stays bounded while another grows without bound. AI assistants by OpenAI and by Anthropic were then used extensively in the research and writing of this paper. They proposed key ideas, including the Kneser graph construction and the use of fractional chromatic numbers, gave initial proofs, and produced much of the drafting. The author directed the subsequent work, also AI-assisted, to understand the mechanisms behind the proofs, determine how far the arguments extend, and develop a general theory of pathology for graph ideals. The general results presented here emerged from this work. He is responsible for the correctness of the paper, including any errors that remain.

Tools used

OpenAI
ChatGPT
Anthropic
Claude Opus
OpenAI
Codex

References

  1. Alon, Noga; Drewnowski, Lech; Ł uczak, Tomasz. Stable Kneser hypergraphs and ideals in N\mathbb{N} with the Nikodým property. Proc. Amer. Math. Soc., vol. 137, no. 2, pp. 467–471. 2009DOI
  2. Alon, Noga; Spencer, Joel H. The probabilistic method. John Wiley & Sons, Inc., Hoboken, NJ, pp. xiv+375. 2016
  3. Beros, Konstantinos A. Universal subgroups of Polish groups. J. Symb. Log., vol. 79, no. 4, pp. 1148–1183. 2014DOI
  4. Borodulin-Nadzieja, Piotr; Farkas, Barnabás. Analytic P-ideals and Banach spaces. J. Funct. Anal., vol. 279, no. 8, pp. 108702, 31. 2020DOI
  5. Borodulin-Nadzieja, Piotr; Farkas, Barnabás; Plebanek, Grzegorz. Representations of ideals in Polish groups and in Banach spaces. J. Symb. Log., vol. 80, no. 4, pp. 1268–1289. 2015DOI
  6. Brattka, Vasco; Rakotoniaina, Tahina. On the uniform computational content of Ramsey's theorem. J. Symb. Log., vol. 82, no. 4, pp. 1278–1316. 2017DOI
  7. Cameron, Peter J. The random graph. The mathematics of Paul Erdős, II, vol. 14, pp. 333–351. 1997DOI
  8. Cano, Julián C.; Di Prisco, Carlos A.; Uzcátegui-Aylwin, Carlos. Combinatorics of Ramsey ideals. 2026. Preprint, \textttarXiv:2606.25477v1 (https://arxiv.org/abs/2606.25477v1)arXiv
  9. Clarke, F. H.; Jamison, R. E. Multicolorings, measures and games on graphs. Discrete Math., vol. 14, no. 3, pp. 241–245. 1976DOI
  10. de Bruijn, N. G.; Erdős, P. A colour problem for infinite graphs and a problem in the theory of relations. Nederl. Akad. Wetensch. Proc. Ser. A, vol. 54, no. 5, pp. 371–373. 1951link
Show all 32 referencesShow fewer references
  1. Erdős, P. Some remarks on the theory of graphs. Bull. Amer. Math. Soc., vol. 53, pp. 292–294. 1947DOI
  2. Farah, Ilijas. Analytic quotients: theory of liftings for quotients over analytic ideals on the integers. Mem. Amer. Math. Soc., vol. 148, no. 702, pp. xvi+177. 2000DOI
  3. Figueroa-Sierra, Raúl. \hrefhttps://repositorio.uniandes.edu.co/bitstreams/4b534792-2ad1-40cb-a1f8-e7d656911474/downloadCombinatorics of ideals on ω\omega: the Category Dichotomy and the Measure Dichotomy. 2025
  4. Filipów, Rafał; Tryba, Jacek. Path of pathology. 2025. Preprint, \textttarXiv:2501.00503v1 (https://arxiv.org/abs/2501.00503v1); version dated January 3, 2025link
  5. Galvin, Fred; Prikry, Karel. On Kelley's intersection numbers. Proc. Amer. Math. Soc., vol. 129, no. 2, pp. 315–323. 2001DOI
  6. Gimbel, John; Kündgen, André; Molloy, Michael. Fractional cocoloring of graphs. Graphs Combin., vol. 38, no. 3, pp. Paper No. 64, 11. 2022DOI
  7. Girão, António; Illingworth, Freddie; Powierski, Emil; Savery, Michael; Scott, Alex; Tamitegama, Youri; Tan, Jane. Induced Subgraphs of Induced Subgraphs of Large Chromatic Number. Combinatorica, vol. 44, pp. 37–62. 2024DOI
  8. Hrušák, M.; Meza-Alcántara, D.; Thümmel, E.; Uzcátegui, C. Ramsey type properties of ideals. Ann. Pure Appl. Logic, vol. 168, no. 11, pp. 2022–2049. 2017DOI
  9. Hrušák, Michael. Combinatorics of filters and ideals. Set theory and its applications, vol. 533, pp. 29–69. 2011DOI
  10. Hrušák, Michael. Katětov order on Borel ideals. Arch. Math. Logic, vol. 56, no. 7-8, pp. 831–847. 2017DOI
  11. Hrušák, Michael; Meza-Alcántara, David. Katětov order, Fubini property and Hausdorff ultrafilters. Rend. Istit. Mat. Univ. Trieste, vol. 44, pp. 503–511. 2012
  12. Kechris, Alexander S. Classical descriptive set theory. Springer-Verlag, New York, vol. 156, pp. xviii+402. 1995DOI
  13. Kelley, J. L. Measures on Boolean algebras. Pacific J. Math., vol. 9, pp. 1165–1177. 1959link
  14. Jordi López-Abad; Víctor Olmos-Prieto; Carlos Uzcátegui-Aylwin. FσF_\sigma-ideals, colorings, and representation in Banach spaces. 2025. Preprint, \textttarXiv:2501.15643v1 (https://arxiv.org/abs/2501.15643v1)arXiv
  15. Lovász, L. Kneser's conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, vol. 25, no. 3, pp. 319–324. 1978DOI
  16. Martínez, Jorge; Meza-Alcántara, David; Uzcátegui, Carlos. Pathology of submeasures and FσF_{\sigma} ideals. Arch. Math. Logic, vol. 63, no. 7-8, pp. 941–967. 2024DOI
  17. Mazur, Krzysztof. FσF_\sigma-ideals and ω1ω1∗\omega_1\omega_1^*-gaps in the Boolean algebras P(ω)/IP(\omega)/I. Fund. Math., vol. 138, no. 2, pp. 103–111. 1991DOI
  18. Prömel, Hans Jürgen; Rödl, Vojtěch. Non-Ramsey graphs are clog⁡nc\log n-universal. J. Combin. Theory Ser. A, vol. 88, no. 2, pp. 379–384. 1999DOI
  19. Scheinerman, Edward R.; Ullman, Daniel H. Fractional graph theory. John Wiley & Sons, Inc., New York, pp. xviii+211. 1997. A rational approach to the theory of graphs, With a foreword by Claude Berge, A Wiley-Interscience Publication. Locators refer to the authors\textquotesingle electronic edition (2008)
  20. Solecki, Sławomir. Analytic ideals and their applications. Ann. Pure Appl. Logic, vol. 99, no. 1-3, pp. 51–72. 1999DOI
  21. Thomas, Simon. Reducts of random hypergraphs. Ann. Pure Appl. Logic, vol. 80, no. 2, pp. 165–193. 1996DOI
  22. Tryba, Jacek. Connections between matrix summability ideals and nonpathological analytic P-ideals. Fund. Math., vol. 265, no. 1, pp. 1–13. 2024DOI

Version history

  1. v1Submitted by Carlos López-CallejasInitial depositCurrentOct 29, 2026