Skip to main content

Section 14.4 David Conlon

David Conlon is an Irish mathematician who works as a professor at the California Institute of Technology. His main research interests are in Ramsey theory, combinatorics, graph theory, pseudorandomness and random graphs.[14.4.3.1] Conlon proved the first superpolynomial bound on the Erdős–Szekeres bound on diagonal Ramsey numbers. Conlon has been awarded the Whitehead Prize (2019) and the European Prize in Combinatorics (2011) [14.4.3.3]. Conlon and our instructor Dr. Veselin Jungić co–authored a paper. [14.4.3.6] and

Subsection 14.4.1 Conlon's favourite proof

One of Conlon's favourite proofs is the proof of Kříž's theorem. In Conlon's words:

One theorem that I think is very interesting and beautiful and should be better known is Kříž's theorem, which, among other things, says that every regular polygon is Ramsey. What this means is that for any \(k\) and \(r\) there is \(d\) such that if we colour in the points of \(\mathbb{R}^d\) in \(r\) colours, then there is a regular \(k\)–gon of side length exactly \(1\) such that all of its \(k\) vertices have the same colour. The interesting part is that we can fix the side length. If we were allowed to dilate, we can already find such a regular \(k\)–gon in any \(r\)–colouring of \(\mathbb{R}^2\text{.}\) [14.4.3.4]

Kříž's theorem was proven by a Czech mathematician Igor Kříž in his paper, Permutation Groups in Euclidean Ramsey Theory. [14.4.3.5] The problem regarding "what configurations \(F\) in a Euclidean space are Ramsey" was first asked by Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus. Kříž's theorem states that every regular polygon is Ramsey.

The proof for this theorem uses induction. We follow [14.4.3.5].

Assume \(F\) is \(\overline{E}\)–Ramsey where \(\overline{E} = \cup(E; z,\ b,\ n - 1)\text{.}\) Choose a \(k \in \mathbb{N}\text{.}\) Now let \(t = |\text{Orb}_b(z)|\) where \(\text{Orb}_b(x) = \{b^nx | n \in \mathbb{N}\}\text{.}\)

Now Let \(m \in \mathbb{N}\) be such that for each \(\tau:\ \binom{m}{t - 1} \rightarrow k^{n - 1}\) there is an \(M \subseteq m\) which is \(M = |t|\) and \(\tau \binom{M}{t - 1}\) is constant. Now there is an \(N \in \mathbb{N}\) such that for each mapping, there is an isometrical embedding \(\psi: F^m \rightarrow \mathbb{R}^N\) that satisfies \(x \overline{E}^m y \Rightarrow \sigma \psi (x) = \sigma \psi (y)\text{.}\)

Now, for \(\{p_1 \lt \cdots \lt p_{t-1}\} = P \in \binom{m}{t - 1}\) and for \(i \in m - 1\text{,}\) define \(u_i(P) \in F^m\) by \((u_i(P))_j = b^i \overline{z}\) for \(j \notin P\text{,}\) \(({u_i(P))_p}_s = b^{i + s}z\) for \(1 \leq s \leq t - 1\text{.}\)

Define \(\tau: \binom{m}{t - 1} \rightarrow k^{n-1}\) by \((\tau(P))_i = \sigma \psi u_i (P)\) for \(i \in n - 1\text{.}\) Let \(M = \{p_0 \lt \cdots \lt p_{t-1}\}\) satisfy the previous two conditions for \(M\text{,}\) and define an embedding \(\overline{\phi}: F \rightarrow F^m\) by \((\overline{\phi}(x))_j = z\) for \(j \notin M\text{.}\) \({(\overline{\phi}(x))_j}_s = b^sz\) for \(0 \leq s \leq t - 1\text{.}\)

Now we have \(xEy \Rightarrow \overline{\phi}(x)E^m\overline{\phi}(y)\) and \(xEy \Rightarrow \sigma \psi \overline{\phi}(x) = \sigma \psi \overline{\phi}(y)\text{.}\)

We need to prove that \((\forall i \in \{1, ..., n - 1\}, (\sigma \psi \overline{\phi} (b^{i - 1}z) = (\sigma \psi \overline{\phi} (b^iz))\text{.}\)

Define \(u(i, j) \in F^m\) by \((u(i, j))_r = b^iz\) for \(r \notin M\text{.}\) \({(u(i, j))_p}_s = b ^ {j+s} z\) for \(r \in M\text{.}\) We have,

\begin{equation*} \sigma \psi \overline{\phi}(b^{i-1}z) = \sigma \psi (u(i - i, i - 1)) = \sigma \psi (u_{i - 1}(M\backslash \{\min M\}))\\ =\sigma \psi (u_{i - 1}(M\backslash \{\max M\})) = \sigma \psi (u(i - 1, i)) = \sigma \psi \overline{\phi}(b^i, z)\text{.} \end{equation*}

Now consider, \(t^{1/2} \cdot F\text{.}\) This is \(t^{1/2} \cdot \cup (E;\ z,\ b,\ n)\)–Ramsey, which means that \(F\) is \(\cup (E;\ z,\ b,\ n)\)–Ramsey and this concludes the proof. [14.4.3.5]

Subsection 14.4.2 Reflections

This proof is incredibly dense. This document skimmed through the proof. The paper by Kříž gives the entire proof. [14.4.3.5]

References 14.4.3 References

[1]
  

California Institute of Technology. (n.d.). David Conlon. Retrieved March 17, 2024, from CALTECH

[2]
  

Conlon, D. (n.d.). A New Upper Bound For Diagonal Ramsey Numbers.Thesis

[3]
  

David Conlon. (2024, January 17). Wikipedia. Retrieved April 7, 2024, from Wikipedia

[4]
  

David Conlon. Personal Communication. February 12, 2024.

[5]
  

Kříž, I. (1991). Permutation Groups in Euclidean Ramsey Theory. Proceedings of the American Mathematical Society, 112(3), pp. 899–907.

[6]
  

Conlon, D., Jungić, V., Radoičić, R. (2007)On the existence of rainbow 4-term arithmetic progressions, Graphs and Combinatorics, 23, 249–254