Embedding theorems for graphs establishing negative partition relations
type: Item
instance of: scholarly article
title: Embedding theorems for graphs establishing negative partition relations
zbMATH Open document ID: 0381.04004
DOI: 10.1007/BF02018087
author: Andras Hajnal
author: P. Erdős
published in: Periodica Mathematica Hungarica
publication date: 1978-01-01T00:00:00Z
review text: The graph \(G_1\) is said to embed into the graph \(G_1\) if \(G_0\) is isomorphic to a spanned subgraph of \(G_1\). Given cardinal numbers \(\varkappa\) and \(\lambda\), the symbol \([\varkappa]\) denotes the complete graph on \(\varkappa\) vertices, \([\varkappa\lambda]\) the complete \((\varkappa\lambda)\)-bipartite graph and , \([\varkappa/\varkappa]\) the half \((\varkappa/\varkappa)\)-bipartite graph (where the set of vertices is a disjoint union \(G_0\cup G_1\) with \(|G_0| = |G_1| = \varkappa\) and there are one-to-one enumerations \(G_0 = \{x_{\alpha};\alpha< \varkappa\}\), \(G_1=\{y_{\beta};\beta< \varkappa\}\) such that for each \(x_{\alpha}\), the set of vertices adjacent to \(x_{\alpha}\) is \(\{y_{\beta};\alpha< \beta< \varkappa\}\)). Let \(\triangle_0\), \(\triangle_1\) be symbols of these types: The graph \(G\) is said to establish the negative partition relation \(\varkappa\nrightarrow(\triangle_0,\triangle_1)^2\) if \(G\) is a graph on \(\varkappa\) vertices such that \(G\) contains no subgraph of type \(\triangle_0\) and the complement of \(G\) contains no subgraph of type \(\triangle_1\). The main aim of this paper is to characterize the class of all countable graphs which embed into all graphs \(G\) establishing \(\aleph_1\nrightarrow(\triangle_0,\triangle_1)^2\) when \(\triangle_0\), \(\triangle_1\) are any of \([\aleph_1]\), \([\aleph_1,\aleph_1]\), \([\aleph_1/\aleph_1]\), \([\aleph_0,\aleph_1]\), The authors prove their theorems in ZFC, and then try to show that they are ''best possible'' assuming the continuum hypothesis or the existence of a Souslin tree. Occasionally Souslin's axiom is invoked instead.
reviewed by: Neil H. Williams
Mathematics Subject Classification ID: 03E05
Mathematics Subject Classification ID: 03E30
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3592000
MaRDI profile type: Publication
cites work: Partition relations for cardinal numbers
cites work: Incompactness in languages with infinitely long expressions
cites work: Colouring without triangles and partition relation
cites work: Iterated Cohen extensions and Souslin's problem
full work available at URL: https://doi.org/10.1007/bf02018087
OpenAlex ID: W2049763138
description: scientific article; zbMATH DE number 3592000