If every uncountable subset of an infinite graph has an infinite clique, must the graph have an uncountable clique?

154 Views Asked by At

Let $G$ be an uncountably infinite graph. $G$ has the property that every uncountable set of nodes includes an infinite clique. Must $G$ contain an uncountable clique?

A simple proof would be to try a Ramsey theorem-like approach to the contrapositive and say "no uncountable clique implies uncountable independent set", but this is apparently not true (Theorem 3.1). I'm worried this problem might just be way over my head and I'll waste a lot of time thinking about it.

1

There are 1 best solutions below

2
On BEST ANSWER

The same counterexample as to the Ramsey theorem you suggest works for your question. Let $<^*$ be a well-ordering of $\mathbb{R}$ and consider the graph on $\mathbb{R}$ with an edge between $x,y\in\mathbb{R}$ if $<^*$ agrees with the usual ordering $<$ on $\{x,y\}$. Since there is no uncountable well-ordered subset of $\mathbb{R}$ with respect to the usual ordering, there is no uncountable clique.

However, I claim every uncountable subset of $\mathbb{R}$ contains an infinite clique. Indeed, suppose $A\subseteq\mathbb{R}$ is uncountable. Replacing $A$ by a subset, we may assume that $A$ has order-type $\omega_1$ with respect to $<^*$. Let $B=\{x\in\mathbb{R}:[x,\infty)\cap A\text{ is countable}\}$ and $x=\inf B$. Since there is a sequence of points of $B$ that approach $x$ from above, $x\in B$, so $B\cap A$ is countable. This means that replacing $A$ with $A\setminus B$, we may assume that for each $a\in A$, $A\cap[a,\infty)$ is uncountable.

Now we construct an infinite clique in $A$. Pick any element $a_0\in A$. Since $A$ has order-type $\omega_1$, all but countably many $b\in A$ satisfy $a_0<^* b$. Since $A\cap [a_0,\infty)$ is uncountable, this means we can pick $a_1\in A$ such that $a_0<a_1$ and $a_0<^* a_1$. We can then similarly find $a_2\in A$ such that $a_1<a_2$ and $a_1<^* a_2$. Continuing this process, we can recursively construct a sequence $(a_n)$ in $A$ which is strictly increasing with respect to both orders. This gives an infinite clique in $A$.