No label defined (Q4660718)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2151248
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 2151248

      Statements

      0 references
      0 references
      4 April 2005
      0 references
      graph homomorphism
      0 references
      long range action
      0 references
      circular chromatic number
      0 references
      The authors ask: ``Suppose some token takes a walk on a connected graph \(H\), stepping from node to adjacent node at each tick of a clock. If we know its position at time 0, can we deduce anything about its position at time \(t\) for large \(t\)?'' Since the answer is yes if \(H\) is bipartite and no if \(\chi(H)>2\) for large \(t\), this property, the authors observe, could be taken as an alternate definition of 2-colourability. In this paper they therefore seek an extension analogous to \(k\)-colourability. Their main result is that if \(H\) is \(k\)-colourable, then \((k-1)\)-branching walks on \(H\) exhibit long range action. A \(d\)-branching walk occurs when, at each step, the token divides into \(d\) (labelled) tokens all of which step at the next tick. Long range action means that the position of a token at time 0 constrains the configuration of its descendents arbitrarily far into the future. But long range action is only one of several properties studied in this wide-ranging paper. Expressing a \(d\)-branching walk on \(H\) as a graph homomorphism from the complete \(d\)-branching tree to \(H\), all these properties are shown to be related to the chromatic number but based on viewing \(H\) as the range, instead of the domain, of a graph homomorphism. The properties studied are based on combinatorial forms of probabilistic concepts from statistical physics, and the authors do a very good job at convincing the reader that these notions are natural and interesting within graph theory. For the entire collection see [Zbl 1051.05003].
      0 references

      Identifiers