Infinite hulls

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 Xv to an infinite clique, and extend f by setting f(v)=f(w).

But I don’t know the answers to the following questions:

  1. Suppose that X is a countably infinite hull and ω(X) is finite. Is it true that χ(X)=ω(X)?
  2. 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.

About these ads

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems, synchronization. Bookmark the permalink.

8 Responses to Infinite hulls

  1. Qiaochu Yuan says:

    This sounds like a good question for MathOverflow!

  2. 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.

  3. Dima says:

    How do hulls relate to graphs with complete core?

  4. 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.

  5. Dima says:

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

    for each finite subgraph \Gamma one has \chi(\Gamma)\leq\omega(X), as for any pair of non-adjacent vertices a,b of \Gamma there will be g\in End(X) such that g(a)=g(b); thus there will be g'\in End(X) so that g'(\Gamma) is a clique
    one can view X is the union of an increasing chain of finite subgraphs \Gamma_1\subset\Gamma_2\dots; for each \Gamma_i one can select an increasing subsequence \{\Gamma_j\} starting at \Gamma_i so that for each graph in it there will be a colouring \mu_j so that \mu_j resticted to \Gamma_i equals to \mu_i.
    It follows that there will be a proper colouring of X in at most \omega(X) colours.

  6. Dima says:

    PS. The PhD student in question is Nick Gravin:
    http://logic.pdmi.ras.ru/~gravin/

  7. Thanks. I have included his proof in the notes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s