×

zbMATH — the first resource for mathematics

The Rado path decomposition theorem. (English) Zbl 1429.05062
Summary: Let \(c : [\omega]^2 \rightarrow r\). A path of color \(j\) is a listing (possibly empty) of integers \(\{a_0, a_1, a_2, \dots\}\) such that, for all \(i \geq 0\), if \(a_{i+1}\) exists then \(c(a_i, a_{i+1} = j\). An empty list can be a path of any color. A singleton can be a path of any color. Paths might be finite or infinite. The color is determined for paths of more than one node. Improving on a result of P. Erdős (oral communication), R. Rado [Ann. Discrete Math. 3, 191–194 (1978; Zbl 0388.05031)] published a theorem which implies: Rado path decomposition: Let \(c : [ \omega ]^2 \rightarrow r\). Then, for each \(j < r\), there is a path of color \(j\) such that these \(r\) paths (as sets) partition \(\omega\) (so they are pairwise disjoint sets and their union is everything). Here we will provide some results and proofs which allow us to analyze the effective content of this theorem.
MSC:
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Keywords:
path of color
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Elekes, M.; Soukup, D. T.; Soukup, L.; Szentmiklóssy, Z., Decompositions of edge-colored infinite complete graphs into monochromatic paths, Discrete Mathematics, 340, 2053-2069 (2017) · Zbl 1362.05102
[2] Enayat, A., From bounded arithmetic to second order arithmetic via automorphisms, Logic in Tehran, 26, 87-113 (2006) · Zbl 1107.03038
[3] Feferman, S., Some applications of the notions of forcing and generic sets, Fundamenta Mathematicae, 56, 325-345 (1965) · Zbl 0129.26401
[4] Gerencsér, L.; Gyárfás, A., On Ramsey-type problems, Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae. Sectio Mathematica, 10, 167-170 (1967) · Zbl 0163.45502
[5] Graham, R. L.; Rothschild, B. L.; Spencer, J. H., Ramsey Theory (1990), John Wiley & Sons, New York: Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York
[6] D. R. Hirschfeldt, Slicing the Truth, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, Vol. 28, World Scientific, Hackensack, NJ, 2015.
[7] Jech, T., Set Theory (2003), Berlin: Springer Monographs in Mathematics, Springer, Berlin
[8] Jockusch, C. G Jr.; Stephan, F., A cohesive set which is not high, Mathematical Logic Quarterly, 39, 515-530 (1993) · Zbl 0799.03048
[9] Kreuzer, Alexander P., NON-PRINCIPAL ULTRAFILTERS, PROGRAM EXTRACTION AND HIGHER-ORDER REVERSE MATHEMATICS, Journal of Mathematical Logic, 12, 1, 1250002 (2012) · Zbl 1269.03021
[10] Pokrovskiy, A., Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Journal of Combinatorial Theory. Series B, 106, 70-97 (2014) · Zbl 1300.05260
[11] Rado, R., Monochromatic paths in graphs, Annals of Discrete Mathematics, 3, 191-194 (1978) · Zbl 0388.05031
[12] Soukup, D. T., Decompositions of edge-coloured infinite complete graphs into monochromatic paths II, Israel Journal of Mathematics, 221, 235-273 (2017) · Zbl 1375.05108
[13] Towsner, Henry, Ultrafilters in reverse mathematics, Journal of Mathematical Logic, 14, 1, 1450001 (2014) · Zbl 1301.03018
[14] R. Weber, Computability Theory, Student Mathematical Library, Vol. 62, American Mathematical Society, Providence, RI, 2012.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.