A universal partition result for infinite homogeneous K-n-free and related graphs

We study new partition properties of infinite K-n-free graphs. First, we investigate the number bpi(G, m) introduced by A. Aranda et al. (denoted there by r(G, m)) : the minimal r so that for any partition of G into r classes of equal size, there exists an independent set which meets at least m classes in size vertical bar G vertical bar. In the case of Henson's countable universal K-n-free graph H-n, we express bpi(H(n)m) by well-known Ramsey-numbers for finite digraphs. In particular we answer a conjecture of Thomasse (2000) by showing that indeed bpi(H-n, 2) = 2 for all n >= 3. Furthermore, we bound and in some cases determine bpi(G, m) for certain geometric graphs, including shift graphs, unit distance graphs and orthogonality graphs.

Second, we prove a new universal partition property for H-n. Given a finite bipartite graph G on classes A, B, we show that for any balanced 2-colouring of H-n there is an induced copy of G in H-n so that the images of A and B are monochromatic of distinct colours. We end our paper with further open problems. (C) 2020 Elsevier B.V. All rights reserved.