OFFSET
1,2
COMMENTS
Let G be any countable universal triangle-free graph. By universality we mean that every countable triangle-free graph is isomorphic to an induced subgraph of G. For every integer n and every finite coloring of the n-element independent sets of G, there exists an induced subgraph H isomorphic to G such that the number of colors used on the n-element independent sets within H is at most a(n). Conversely, there exists a coloring of the n-element independent sets of G with a(n) colors such that every induced subgraph isomorphic to G uses all a(n) colors.
The term big Ramsey degree was introduced by Kechris, Pestov, and Todorcevic (2005). The first element of the sequence was determined by Komjáth and Rödl (1986). The existence of the infinite sequence was proved by Dobrinen (2020) with shorter proofs given by Zucker (2022) and Hubička (2025). The exact sequence was characterized by Balko, Chodounský, Dobrinen, Hubička, Konečný, Vena, and Zucker (2024), with an easier presentation provided by the same authors in arXiv:2303.10088. The first 10 elements of the sequence were computed by Konečný, Hubička, Vodseďálek, and Zucker (2025).
REFERENCES
M. Balko, D. Chodounský, N. Dobrinen, J. Hubička, M. Konečný, L. Vena, A. Zucker, Exact big Ramsey degrees for finitely constrained binary free amalgamation classes, Journal of the European Mathematical Society, 2024, published online first.
N. Dobrinen, The Ramsey theory of the universal homogeneous triangle-free graph, Journal of Mathematical Logic, 20 (2020), 2050012.
J. Hubička, Big Ramsey degrees using parameter spaces, Advances in Mathematics 478 (2025), 110386.
J. Hubička, M. Konečný, Š. Vodseďálek, A. Zucker, Counting big Ramsey degrees of the homogeneous and universal K_4-free graph, arXiv:2505.22620, extended abstract accepted to Eurocomb 2025.
A. S. Kechris, V. G. Pestov, S. Todorcevic, Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geometric and Functional Analysis 15(1) (2005), 106-189.
P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs and Combinatorics 2(1) (1986) 55-60.
N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1-3) (1998) 137-181.
Š. Vodseďálek, Counting big Ramsey degrees, Bachelor's thesis, Charles University (2025).
A. Zucker, On big Ramsey degrees for binary free amalgamation classes, Advances in Mathematics 408 (2022), 108585
LINKS
M. Balko, D. Chodounský, N. Dobrinen, J. Hubička, M. Konečný, L. Vena, and A. Zucker, Characterisation of the big Ramsey degrees of the generic partial order, arXiv:2303.10088 [math.CO], 2025.
J. Hubička and A. Zucker, A survey on big Ramsey structures, arXiv:2407.17958 [math.LO], 2025.
CROSSREFS
KEYWORD
nonn,hard
AUTHOR
Jan Hubicka and Stepan Vodsedalek, Aug 27 2025
STATUS
approved