Erdos 1975 set systems having large chromatic number

../

corollary_10_7: Erdős, Galvin and Hajnal's evaluation, assuming 2^{aleph_alpha} = aleph_{alpha+1}, of the least number of triples on n points that a triple system on aleph_{alpha+1} without free aleph_{alpha+1}-sets must allow: the integer part of (n-1)^2/4.

corollary_11_14: Erdős, Galvin and Hajnal's evaluation under GCH of the least number of triples on m points that an aleph_{alpha+1}-chromatic triple system on aleph_{alpha+1} points must allow: the integer part of m^2/8.

problem_10: Erdős, Galvin and Hajnal's problem to characterize the finite triple systems contained in every triple system of chromatic number greater than aleph_0, with four simplest unsolved instances and related questions.

problem_3: Erdős, Galvin and Hajnal's open question whether every graph of infinite chromatic number kappa has its edges split into kappa classes so that every vertex colouring with fewer than kappa colours has a colour class containing an edge of each class, with the weaker two-class version for aleph_1.

problem_9: Erdős, Galvin and Hajnal's problem to characterize the finite triple systems occurring in every aleph_1-chromatic triple system on omega_1, with what they know about the class G_3(omega_1) and five related open questions.

theorem_14_4: Erdős, Galvin and Hajnal's theorem that every triple system of chromatic number above aleph_0 has t-point sets spanning at least g-check_3(t) triples, that for every infinite kappa some triple system of chromatic number above kappa has none spanning more, and that g-check_3(t) lies between (t/3)^{3/2} - t and (t/3)^{3/2}.

theorem_14_6: Erdős, Galvin and Hajnal's extension of Theorem 14.4 to n-tuple systems: for every infinite kappa some n-tuple system of chromatic number above kappa has at most g-check_n(t) members inside every t points, where g-check_n(t) <= (t/n)^{n/(n-1)} and g-check_n(n t^{n-1}) = t^n.

theorem_2_1: Erdős, Galvin and Hajnal's generalization of the Erdős–Hajnal bipartite theorem: for some positive integer m, a (k + 2)-tuple system of chromatic number above aleph_alpha has, for every finite t, aleph_{alpha+m} points each joined, together with any of t disjoint (i_m + 1)-sets, inside a tuple of the system.

theorem_3_8: Erdős, Galvin and Hajnal's theorem that a triple system of chromatic number above aleph_alpha either contains, for every finite t, t disjoint pairs with aleph_{alpha+1} common apexes, or contains, for every finite t, aleph_{alpha+1} disjoint copies of K(t,t) whose edges all reach a fixed set of t^2 points.

theorem_b: Erdős, Galvin and Hajnal's theorem that for mi + 2 <= n every (n, i, aleph_alpha)-system of size aleph_{alpha+m} has chromatic number at most aleph_alpha, while for n < mi + 2 under GCH some (n, i)-system of size aleph_{alpha+m} has chromatic number above aleph_alpha.

---

P. Erdős, F. Galvin, A. Hajnal: On set-systems having large chromatic number and not containing prescribed subsystems, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I; Colloq. Math. Soc. János Bolyai, Vol. 10, pp. 425--513, North-Holland, Amsterdam, 1975 (MR 53 #2727; Zentralblatt 324.04005). No notice is printed in the file (pp. 1--2 and 88--89 read); the hosting archive's site footer speaks for the site, not the paper (https://users.renyi.hu/~p_erdos/, read: "(C) 2005-2007 All rights reserved. All material on this site is for scientifics purposes only."); the colloquium volume has no online publisher edition or DOI, so the publisher's page was not consulted and no Crossref license is recorded; the term is unstated.

This 89-page memoir develops the theory of chromatic numbers of set systems (n-uniform hypergraphs), taking the Erdős–Hajnal theory as its starting point. Theorem A recalled in the introduction is the Erdős–Hajnal result that a graph of chromatic number greater than an infinite cardinal kappa contains K(t, kappa^+) for every finite t; the authors note (p. 426) that the 1966 Erdős–Hajnal paper proving Theorem A also claimed a generalization to n-tuple systems with 3 at most n at most omega, and that it is false: by the paper of Erdős, Hajnal and Rothschild (reference [12]), a triple system on at most aleph_1 vertices with chromatic number above aleph_0 has two triples meeting in two points, but on larger vertex sets the chromatic number of a system of pairwise edge-disjoint triples can be arbitrarily large. The paper therefore studies (n, i, lambda)-systems, in which every set of i + 1 vertices lies in at most lambda edges, and asks how large the vertex set of such a system of chromatic number greater than kappa must be; Sections 2 to 16 give a theorem restricting the chromatic number of relatively small n-tuple systems (Theorem 2.1) with corollaries bounding the functions h_3(t, alpha), g_n(t, alpha), a general theorem for set systems, consequences of Martin's axiom, simultaneous chromatic numbers, graph constructions, constructions of small n-tuple systems without large free sets, of 3-circuitless n-tuple systems of large chromatic number, and of the smallest large-chromatic triple systems, closing with problems. The paper's Problem 10 (p. 498), to characterize the finite triple systems that occur in every triple system of chromatic number greater than aleph_0, is the question of Problem 593; the paper proves partial results toward it and leaves it open.

Source: https://users.renyi.hu/~p_erdos/1975-24.pdf.

Bears on. #593: the paper's Problem 10 (p. 498) asks the problem's question, the characterization of the finite triple systems occurring in every triple system of chromatic number greater than aleph_0, and leaves it open; Theorem 3.8 (p. 438) is the positive result the paper names toward it (p. 499), and Theorem 14.4 (p. 495) bounds by edge density which finite triple systems can be forced. #1176: Problem 3 of Section 6 (p. 449) asks whether every graph G of chromatic number kappa >= aleph_0 satisfies P(G, kappa, kappa), which for kappa = aleph_1 is the problem's edge-colouring question; the paper leaves it open. #1177: Problems 9/D (p. 482) and 10.B (p. 499) ask the problem's second assertion for aleph_1-chromatic triple systems on omega_1 and for triple systems of chromatic number greater than aleph_0 respectively, 9/E (p. 482) asks whether the classes G_3(kappa) of finite triple systems forced in kappa-chromatic systems on kappa agree for all infinite kappa, and 10.D (p. 499) asks for a triple system on 2^{2^aleph_0} vertices of chromatic number greater than aleph_0 whose finite subsystems all embed in a given such system, a yes to which would give the problem's first assertion with chromatic number greater than aleph_0 in place of aleph_1; the paper poses them as open.

Results.

• Theorem A (Section 0, p. 426), recalled from Erdős and Hajnal's 1966 paper (Theorem 5.5 there, recorded at theorem_5_5): if kappa is an infinite cardinal and a graph has chromatic number greater than kappa, then it contains a complete bipartite graph K(t, kappa^+) for every finite t.
• Section 0 (p. 426), citing reference [12]: the simplest instance of the claimed generalization of Theorem A, that a triple system of chromatic number greater than aleph_0 has two triples with a common edge, holds only when the vertex set has cardinality at most aleph_1; on larger vertex sets there are triple systems of arbitrarily large chromatic number consisting of edge-disjoint triples.
• Theorem B (p. 427): for mi + 2 <= n < aleph_0 every (n, i, aleph_alpha)-system of cardinality aleph_{alpha+m} has chromatic number at most aleph_alpha; for 2 <= n < mi + 2 < aleph_0 under GCH some (n, i)-system of cardinality aleph_{alpha+m} has chromatic number greater than aleph_alpha.
• Theorem 2.1 (p. 432), with Corollary 2.2 (p. 433): the generalization of Theorem A to n-tuple systems that gives part (a) of Theorem B.
• Theorem 3.8 (p. 438), with Corollaries 3.9 (p. 439) and 3.10 (p. 440): a triple system of chromatic number greater than aleph_alpha contains the first of two configurations for every finite t, or the second for every finite t, whence g_3(t, alpha) >= (t/3)^{3/2} - t.
• Problem 3 (p. 449): whether every graph G of chromatic number kappa >= aleph_0 satisfies P(G, kappa, kappa), and whether every aleph_1-chromatic graph on omega_1 satisfies P(G, 2, aleph_1); P(S, lambda, kappa) (Definition 6.2, p. 448) says that the edges of S split into lambda classes so that every partition of the vertices into fewer than kappa classes has a class containing an edge from each edge class. The authors note just before it that their proof that some graph on aleph_1 vertices satisfies P(G, aleph_1, aleph_1) needs CH.
• Corollary 10.7 (p. 469): if 2^{aleph_alpha} = aleph_{alpha+1}, then h_3(n, alpha) is the integer part of (n-1)^2/4.
• Corollary 11.14 (p. 481): under GCH, g-hat_3(m, alpha) is the integer part of m^2/8.
• Problem 9 (pp. 481--482): the finite triple systems occurring in every aleph_1-chromatic triple system on omega_1, with questions 9/A to 9/E.
• Theorem 14.4 (p. 495): every triple system of chromatic number greater than aleph_0 has t-point sets with at least g-check_3(t) triples, for every infinite kappa some triple system of chromatic number greater than kappa has none with more, and (t/3)^{3/2} - t <= g-check_3(t) <= (t/3)^{3/2}.
• Theorem 14.6 (p. 498): the corresponding constructions and upper bound g-check_n(t) <= (t/n)^{n/(n-1)} for n-tuple systems, n >= 3.
• Problem 10 (pp. 498--499): the finite triple systems occurring in every triple system of chromatic number greater than aleph_0, with questions 10.A to 10.D.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.