A strong form of König’s lemma

A student proposed to me the following strong form of König’s lemma:

Conjecture. Suppose that $G=(V,E)$ is a countable a graph, and there is a partition of $V$ into countably many pieces $V=\bigcup_{n<\omega}V_n$, such that:

  • for all $n<\omega$, $V_n$ is finite (but nonempty);
  • for all two distinct $n,m<\omega$, for each $x\in V_n$, there is $y\in V_m$ with $\{x,y\}\in E$.

Then there exists an infinite $K\subseteq V$ such that $[K]^2\subseteq E$.

In this post, I will quickly address this “conjecture”. Thus, if you prefer to think about it by yourself, read no more.






Refutation. Consider the graph $G=(\mathbb N,E)$ where $\{n,m\}\in E$ iff $n+m=1\pmod2$. It is easy to see that for every 3-sized set $\{n,m,l\}$, we have $\{n,m,l\}^2\nsubseteq E$. On the other hand, letting $V_n:=\{2n,2n+1\}$ for all $n<\omega$ yields a partition satisfying the above-mentioned properties.

This entry was posted in Blog. Bookmark the permalink.

2 Responses to A strong form of König’s lemma

  1. Ari B. says:

    So the underlying graph is just a complete bipartite graph $K_{\omega,\omega}$ ….


Leave a Reply

Your email address will not be published. Required fields are marked *