David Gunderson

Section 14.7 David Gunderson

David Gunderson is a Canadian mathematician. His main field of work is in combinatorics. Gunderson makes wood into mathematical models in his free time. Gunderson wrote a book on mathematical induction which was published in 2010. Gunderson has multiple publications with Erdős, including one that is directly related to Ramsey theory. [14.7.3.3]

Gunderson and our instructor Dr. Veselin Jungić co–authored a paper on Ramsey theory and Fibonacci numbers. [14.7.3.2]

Subsection 14.7.1 Gunderson's favourite proofs

Professor Gunderson told us that he spent multiple days going through multiple proofs and theorems to try to list favourites. However, it turned out that he had way too many proofs that he liked so he ended up only sharing a few of his favourites.

So instead Dr. Gundarson shared with us his unpublished notes on Ramsey theory and sent us a list with some of the proofs that he really liked. He described the notes in the following way:

Starting with my masters thesis, I began a set of notes on Ramsey theory, and in places, these notes are still rather incomplete. I hope that you find them interesting; at the very worst, there are enough references given so that you can find more (exciting) details. [14.7.3.1]

The first proof that Professor Gunderson listed is by Erdős in 1947.

Theorem 14.7.1.

If \(\binom{n}{k}2^{\binom{n}{2}-\binom{k}{2}+1} \lt 2^{\binom{n}{2}}\) then \(R(k, k) \gt n\text{.}\)

Proof.

Call a graph with \(n\) vertices good if it contains a \(K_k\) or \(k\) independent vertices. The number of good graphs is at most \(\binom{n}{k}2^{\binom{n}{2}-\binom{k}{2}+1}\text{,}\) and the number of graphs on \(n\) vertices is \(2^{\binom{n}{2}}\text{.}\) This means that if \(\binom{n}{k}2^{\binom{n}{2}-\binom{k}{2}+1} \geq 2^{\binom{n}{2}}\) then there exists a graph that is not good.

The second proof that Professor Gunderson lists is another proof by Erdős, this time in 1959.

Theorem 14.7.2.

For all \(k \geq 2\) and \(l \geq 3\text{,}\) there exists a graph \(G\) with \(\text{girth}(G) \gt l\) and \(\chi(G) > k\) (\(\chi(G)\) represent the chromatic number of the graph; girth is the length of the shortest cycle contained in the graph).

Proof.

Let \(k \geq 2\) and \(l \geq 3\text{.}\) Let \(\theta \in \mathbb{R}\) where \(0 \lt \theta \lt\frac{1}{l}\text{.}\) With \(p = n^{\theta - 1}\text{,}\) let \(G \in G(n, p)\) be a random graph on \(n\) vertices, where each pair of vertices is chosen to be an edge randomly and independently with probability \(p\text{.}\) Let \(X = X(G)\) be the random variable counting the number of cycles in \(G\) with length at most \(l\text{.}\) For any set \(S\) on \(i\) vertices, the number of possible cycles on \(S\) is \(\frac{i!}{2i}\text{.}\) By assumption, each cycle \(C_i\) has probability \(p^i\text{.}\) This means the expected value is

\begin{equation*} \mathbb{E}[X] = \sum_{i=3}^l \binom{n}{i} \frac{i!}{2i} p^i \lt \sum_{i=3}^l \frac{n^i}{2i}p^i // = \sum_{i=3}^l \frac{n^{i\theta}}{2i} \lt \frac{l}{6}n^{l\theta} = o(n) \end{equation*}

because \(l\theta \lt 1\text{.}\)

By Markov's inequality, \(\mathbb{P}[X \geq n/2] = o(1)\text{.}\) Set \(x = \lceil (3/p)\ln n\rceil\text{,}\)

\begin{equation*} \mathbb{P}[\alpha(G) \geq x] \leq \binom{n}{x}(1-p)^{\binom{x}{n}} \lt (ne^{(-p(x-1)/2)})^x = o(1)\text{,} \end{equation*}

where \(\alpha(n)\) represents the independence number.

Now let \(n\) be large enough that the two \(o(n)\) terms are less than \(0.5\text{.}\) Then there exists a graph \(G\) where \(X(G) \lt n/2\) and \(\alpha(G) \lt x\text{.}\) This implies that \(G\) has fewer than \(n/2\) cycles which are of length at most \(l\text{,}\) and \(\alpha \lt 3n^{1-\theta}\ln (n)\text{.}\) Let \(G^*\) be a graph obtained by removing one vertex from each cycle of length at most \(l\text{.}\) Now we have girth \((G^*)) \gt l\text{,}\) \(|V(G^*)| \geq n/2\text{,}\) and \(\alpha(G^*)\text{.}\) Now assuming that for a graph \(G,\ \chi(G) \alpha (G) \geq |V(G)|\) we have

\begin{equation*} \chi(G^*) \geq \frac{|V(G^*)|}{\alpha(G^*)} = \geq \frac{n/2}{3n^{1-\theta}\ln (n)} = \frac{n^\theta}{6\ln (n)}\text{.} \end{equation*}

If we let this \(n\) be large that \(\frac{n^\theta}{6\ln (n)} \gt k\text{,}\) we have found our graph.

Both of these proofs come from Professor Gunderson's unpublished notes.

Dr. Gunderson included this probability proof in his list of favourite Ramsey theory proofs as this creates a Ramsey like theorem.

Theorem 14.7.3.

For positive integers \(k \geq 2,\ n, g \geq 3\) there exists a \(k\)–uniform hypergraph \(G \in Forb(C_2, C_3, \ldots, C_g)\) so that \(G \rightarrow (E_G)_n^{K_1}\text{.}\)

Additionally, Gunderson's Ph.D. advisor, Vojtĕch Rödl, created a technique called partite amalgamation which is used to construct the high girth/chromatic number graphs. Partite amalgamation is also used in many Ramsey proofs related to graphs and hypergraphs.

Gunderson also listed the Erdős–Szekeres as another one of his favourites, calling it beautiful.

The last proofs that Gunderson listed are Shelah's proof of the Hales–Jewett theorem, the powers of the Lovasz–Local–Lemma, and ultrafilters and Hindman's theorems.

Gunderson also mentioned that he felt inspired to work on his notes again, so that they may be distributed in the future.

Subsection 14.7.2 Reflection

Gunderson's response was incredible. It was thrilling to see that he has spend days trying to list all of his favourite proofs. Reading that he felt inspired to work on his notes again so that they may be distributed was exciting.

References 14.7.3 References

[1]

David Gunderson. Personal Communication. February 6, 2024.

[2]

Ardal, H., Gunderson, D. S., Jungić, V., Landman, B. M., and Williamson, K., Ramsey Results Involving the Fibonacci Numbers, The Fibonacci Quarterly, Volume 46/47, February 2009, 10-17.

[3]

University of Manitoba. (n.d.). Homepage of David S. Gunderson. University of Manitoba - Information Services and Technology - Personal Server. Retrieved March 17, 2024, from Gunderson.