“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 7412
School of Mathematics
  Title:   Random walks and graph homomorphisms
1.  A. Daneshgar
2.  H. Hajiabolhassan
  Status:   Published
  Journal: DIMACS Ser. Discrete Math. Theoret. Comput. Sci.
  Vol.:  63
  Year:  2004
  Pages:   49-63
  Supported by:  IPM
In this report (whose basic approach is based on [12]) we introduce a general idea which gives rise to some necessary conditions for the existence of graph homomorphisms (directed and undirected), which is mainly based on available comparison techniques for Markov chains. We focus on the finite strongly-connected case to propose the main ideas, however, there are also a variety of conceivable extensions to weaker conditions or the finite case. what follows we specially focus on a combination of Diaconis and Saloff-Coste comparison technique for Markov chains and a generalization of Haemers interlacing theorem to show one possible approach which results in a general no-homomorphism theorem; and after that we also consider some special cases and corollaries which are more appropriate for concrete applications. Specially, when the range is a Cayley graph, we mention a theorem with a corollary about the existence of homomorphisms to odd cycles. This, in particular, provides a proof of the fact that the Coxeter graph is a core. some applications, we introduce 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. the end, we add some concluding notes about the possible extensions and different aspects of our approach, which show some connections to the theory of expanders and Ramanujan graphs as well as some applications of algebraic number theory and group theory to the subject.

Download TeX format
back to top
scroll left or right