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.

### Like this:

Like Loading...

*Related*

## About Peter Cameron

I count all the things that need to be counted.

This sounds like a good question for MathOverflow!

Thanks for the suggestion. I have never used MathOverflow; I had the impression that it is designed for questions where you think somebody else has some information which you don’t have. In this case, it is rather that I thought up a question which I think other people might like thinking about for themselves. The hull of a graph is a relatively new concept and until very recently had only been considered for finite graphs.

How do hulls relate to graphs with complete core?

In the finite case, every hull has complete core, but not conversely. (Every bipartite graph with at least one edge has core the complete graph of order 2; but the only connected bipartite hulls are complete bipartite graphs.)

In the infinite case, paradoxically, the definition of hull is clear whereas that of core is somewhat problematic. But at least “complete core” is fairly clear, and the above implication still holds.

My PhD student tells me (after I explained to him my own totally wrong “proof”) that 1. must be true:

for each finite subgraph one has as for any pair of non-adjacent vertices of there will be such that ; thus there will be so that is a clique

one can view is the union of an increasing chain of finite subgraphs ; for each one can select an increasing subsequence starting at so that for each graph in it there will be a colouring so that resticted to equals to

It follows that there will be a proper colouring of in at most colours.

Nice!

PS. The PhD student in question is Nick Gravin:

http://logic.pdmi.ras.ru/~gravin/

Thanks. I have included his proof in the notes.