✦ LIBER ✦

Graph homomorphisms through random walks

✍ Scribed by Amir Daneshgar; Hossein Hajiabolhassan

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 174 KB
Volume: 44
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10125

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we introduce some general necessary conditions for the existence of graph homomorphisms, which hold in both directed and undirected cases. Our method is a combination of Diaconis and Saloff–Coste comparison technique for Markov chains and a generalization of Haemers interlacing theorem. As some applications, we obtain a necessary condition for the spanning subgraph problem, which also provides a generalization of a theorem of Mohar (1992) as a necessary condition for Hamiltonicity. In particular, in the case that the range is a Cayley graph or an edge‐transitive graph, we obtain theorems with a corollary about the existence of homomorphisms to cycles. This, specially, provides a proof of the fact that the Coxeter graph is a core. Also, we obtain some information about the cores of vertex‐transitive graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 15–38, 2003

📜 SIMILAR VOLUMES

On Random Graph Homomorphisms into Z

✍ Itai Benjamini; Olle Häggström; Elchanan Mossel 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 319 KB

Given a bipartite connected finite graph G=(V, E) and a vertex v 0 # V, we consider a uniform probability measure on the set of graph homomorphisms f : V Ä Z satisfying f (v 0 )=0. This measure can be viewed as a G-indexed random walk on Z, generalizing both the usual time-indexed random walk and tr

Random walks on random simple graphs

✍ Martin Hildebrand 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 676 KB

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (logn)", where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou

Quantum Simulations of Classical Random

Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity

✍ John Watrous 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 160 KB

While it is straightforward to simulate a very general class of random processes space-efficiently by non-unitary quantum computations (e.g., quantum computations that allow intermediate measurements to occur), it is not currently known to what extent restricting quantum computations to be unitary a

Resistance distance in graphs and random

Resistance distance in graphs and random walks

✍ José Luis Palacios 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB 👁 2 views

A Random Walk through the Web

✍ Sabine Klapp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB 👁 1 views

Upper bounds on the height difference of

Upper bounds on the height difference of the Gaussian random field and the range of random graph homomorphisms into ℤ

✍ Itai Benjamini; Gideon Schechtman 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 2 views