Preparing for the course on Synchronization has thrown up some questions to which I don’t know the answer. Here is one.
First, the definitions. A graph homomorphism is a map on the vertices which takes edges to edges; it can do anything to a non-edge (map it to a non-edge, an edge, or a single vertex). An endomorphism is a homomorphism from a graph to itself. The graph X is a hull if, for any two non-adjacent vertices v and w, there is an endomorphism of X mapping v and w to the same vertex. The clique number ω(X) is the size of the largest clique in X (or the supremum of the clique sizes, if X is infinite; the chromatic number χ(X) is the smallest number of colours needed to colour the vertices so that adjacent vertices get different colours.
Now if the finite graph X is a hull, then its clique number and chromatic number are equal. For let f be an endomorphism whose image is as small as possible; then f is a proper colouring, and its image is a clique.
Also, if X is countably infinite and contains an infinite clique, then X is a hull. For suppose that v and w are non-adjacent. Let f be a bijection from X–v to an infinite clique, and extend f by setting f(v)=f(w).
But I don’t know the answers to the following questions:
- Suppose that X is a countably infinite hull and ω(X) is finite. Is it true that χ(X)=ω(X)?
- Is an uncountably infinite graph whose largest clique is countably infinite necessarily a hull?
Ramsey’s celebrated theorem says that an infinite graph contains either an infinite clique or an infinite coclique; but there are uncountable graphs whose largest cliques and cocliques are both countable. But that is a subject for another day.