All reports by Author Martin Dyer:

__
TR05-151
| 7th December 2005
__

Magnus Bordewich, Martin Dyer, Marek Karpinski#### Metric Construction, Stopping Times and Path Coupling.

__
TR05-121
| 17th October 2005
__

Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson#### On counting homomorphisms to directed acyclic graphs

__
TR05-075
| 4th July 2005
__

Martin Dyer, Leslie Ann Goldberg, Mark Jerrum#### Dobrushin conditions and Systematic Scan

Revisions: 1

__
TR05-002
| 6th January 2005
__

Magnus Bordewich, Martin Dyer, Marek Karpinski#### Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

__
TR04-009
| 22nd January 2004
__

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda#### Randomly coloring constant degree graphs

Magnus Bordewich, Martin Dyer, Marek Karpinski

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... more >>>

Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson

We give a dichotomy theorem for the problem of counting homomorphisms to

directed acyclic graphs. $H$ is a fixed directed acyclic graph.

The problem is, given an input digraph $G$, how many homomorphisms are there

from $G$ to $H$. We give a graph-theoretic classification, showing that

for some digraphs $H$, ...
more >>>

Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

We consider Glauber dynamics on finite spin systems.

The mixing time of Glauber dynamics can be bounded

in terms of the influences of sites on each other.

We consider three parameters bounding these influences ---

$\alpha$, the total influence on a site, as studied by Dobrushin;

$\alpha'$, the total influence ...
more >>>

Magnus Bordewich, Martin Dyer, Marek Karpinski

We give a new method for analysing the mixing time of a Markov chain using

path coupling with stopping times. We apply this approach to two hypergraph

problems. We show that the Glauber dynamics for independent sets in a

hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ...
more >>>

Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda

We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree Δ. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> ≥ <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>>