×

Obligatory subsystems of triple systems. (English) Zbl 1199.03029

The paper studies unavoidable configurations in triple systems with uncountable chromatic number, and with no two triples intersecting by 2 points. It is proved that every unavoidable subsystem is tripartite, and can be realised as the collection of rainbow-colored triangles in a finite 3-edge-colored graph.
An infinite series of unavoidable systems is found.

MSC:

03E05 Other combinatorial set theory
03E35 Consistency and independence results
05B07 Triple systems
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Erdos, Graph theory and probability, Canad. Journ. Math., 11 (1959), 34–38. · Zbl 0084.39602
[2] P. Erdos, F. Galvin and A. Hajnal, On set systems having large chromatic number and not containing prescribed subsystems, Colloq. Math. Soc. J. Bolyai, 10 (1975), 425–513. · Zbl 0324.04005
[3] P. Erdos and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hung., 17 (1966), 61–99. · Zbl 0151.33701
[4] P. Erdos, A. Hajnal and B. Rothschild, On chromatic number of graphs and set systems, in: Cambridge Summer School in Mathematical Logic, Lecture Notes in Mathematics, 337 (1973), pp. 531–538.
[5] P. Erdos and R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc., 62 (1956) 427–489. · Zbl 0071.05105
[6] P. Erdos and R. Rado, Partition relations connected with chromatic number of graphs, Journal of London Math. Soc., 34 (1959), 63–72. · Zbl 0084.19701
[7] A. Hajnal, On the chromatic number of graphs and set systems, PIMS Distinguished Chair Lecture Notes, 2004. http://www.pims.math.ca
[8] P. Komjáth, Some remarks on obligatory subsystems of uncountably chromatic triple systems, Combinatorica, 21 (2001), 233–238. · Zbl 0996.05047
[9] P. Komjáth, An uncountably chromatic triple system, to appear.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.