Bipartite graphs and monochromatic squares (Q1732805)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bipartite graphs and monochromatic squares |
scientific article |
Statements
Bipartite graphs and monochromatic squares (English)
0 references
25 March 2019
0 references
Consider a bipartite graph \((U\cup V,E)\); a pair of sets \((A,B)\) with \(A\subseteq U\) and \(B\subseteq V\) is independent if there is no edge from any \(a\in A\) to any \(b\in B\); it is complete if each element of \(A\) is connected to each element of~\(B\). The main result of the paper shows that if \(\theta\) is regular and there is a \((\theta^{++},\theta^{++},\theta)\)-saturated ideal on~\(\theta^{++}\). Then for every colouring \(c:\theta^{++}\times\theta^{++}\to\theta\) and ordinal~\(\alpha\) below~\(\theta^{++}\) there are sets \(A\) and \(B\) of order-type~\(\alpha\) such that \(C\)~is constant on~\(A\times B\). As a consequence every bipartite graph \((\theta^{++}\times2,E)\) has an independent or a complete pair of sets both of any prescribed order type below~\(\theta^{++}\). The existence of an ideal as in the assumptions can be proved consistent from a huge cardinal above~\(\theta\), see [\textit{R. Laver}, Stud. Logic Found. Math. 108, 173--180 (1982; Zbl 0524.03037)].
0 references
bipartite graph
0 references
polarized partition
0 references
saturated ideal
0 references