×

An uncountably chromatic triple system. (English) Zbl 1199.03030

A triple system is a pair \((V,E)\) with \(E \subseteq [V]^3\). Its chromatic number \(\text{Chr}(V,E)\) is the least cardinal \(\mu\) such that there exists a function \(f : V \rightarrow \mu\) such that for each \(\{ x,y,z \} \in E\) we have \(| \{ f(x), f(y), f(z) \}| \geq 2\).
For \(3 \leq n < \omega\), \(\mathcal{C}_n\) is the triple system \((V,E)\) with \(V = \{ x_i, y_i : i<n \}\) and \(E = \{\{x_i,y_i,x_{i+1} \} : i<n \}\) (with \(x_n = x_0\)), and \(\mathcal{T}_0\) is the triple system with vertex set \(\{ x,y,z,t\}\) and triples \(\{ x,y,z\}\), \(\{x,y,t\}\).
In an earlier paper, A. Hajnal and P. Komjáth [Acta Math. Hung. 119, No. 1–2, 1–13 (2008; Zbl 1199.03029)] showed: If an uncountably chromatic triple system omits \(\mathcal{T}_0\), then it contains all odd circuits of length \(\geq 7\). Here the author shows that it is consistent that GCH holds and there is a triple system \(\mathcal {H}\) with \(| \mathcal {H}| = \aleph_2\), \(\text{Chr}(\mathcal {H}) = \aleph_1\) and \(\mathcal {H}\) does not contain \(\mathcal {T}_0\), \(\mathcal {C}_3\) or \(\mathcal {C}_5\).

MSC:

03E05 Other combinatorial set theory
03E35 Consistency and independence results
05B07 Triple systems
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1199.03029

Software:

SCHOL
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, Cambridge Summer Schol in Mathematical Logic, Lecture Notes in Mathematics, 337 (1973), 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.math.rutgers.edu/:_ahajnal/_notes.pdf
[8] A. Hajnal and P. Komjáth, Obligatory subsystems of triple systems, Acta Math. Hungar., 119 (2008), 1–13. · Zbl 1199.03029
[9] P. Komjáth, Some remarks on obligatory subsystems of uncountably chromatic triple systems, Combinatorica, 21 (2001), 233–238. · Zbl 0996.05047
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.