/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
The graph-target ordinal partition relation $\alpha \to (\beta, G)^2$: for every red/blue
colouring of the edges of the complete graph on $\alpha$, either there is a red clique of
order type $\beta$, or there is a blue copy of the graph $G$ (an injective map sending the
edges of $G$ to blue edges).
This generalises OrdinalCardinalRamsey, replacing the blue clique of cardinality $c$
(i.e. a blue copy of $K_c$) by a blue copy of an arbitrary graph $G$.
Will be moved to FormalConjecturesForMathlib/SetTheory/Ordinal/PartitionRelation.lean
once the shared home for ordinal partition relations lands (see PR #4195).
Erdős Problem 597 [Er87]. Let $G$ be a graph on at most $\aleph_1$
vertices which contains no $K_4$ and no $K_{\aleph_0,\aleph_0}$ (the complete bipartite
graph with $\aleph_0$ vertices in each class). Is it true that
$$\omega_1^2 \to (\omega_1 \omega, G)^2?$$
Erdős Problem 597, finite case [Er87]. Is it true that
$\omega_1^2 \to (\omega_1 \omega, G)^2$ for every finite $K_4$-free graph $G$?
(A finite graph contains no $K_{\aleph_0,\aleph_0}$, so that hypothesis is vacuous.)
Erdős and Hajnal proved that $\omega_1^2 \to (\omega_1 \omega, 3)^2$: in every red/blue
colouring of the edges of the complete graph on $\omega_1^2$ there is either a red clique
of order type $\omega_1 \cdot \omega$ or a blue triangle.
Erdős originally asked Problem 597 with just the assumption that $G$ is $K_4$-free, but
Baumgartner proved that $\omega_1^2 \not\to (\omega_1 \omega, K_{\aleph_0,\aleph_0})^2$.
Sanity check: the relation $\omega_1^2 \to (\omega_1 \omega, G)^2$ holds trivially when
$G$ is a single vertex with no edges, since any vertex of $\omega_1^2$ is a blue copy
of $G$.