Skip to main navigation Skip to Content
Paper IPM / M / 7412  


Abstract:  
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
stronglyconnected 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 SaloffCoste comparison technique for Markov chains and a
generalization of Haemers interlacing theorem to show one possible
approach which results in a general nohomomorphism 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 
COPYRIGHT 2012 © ALL RIGHTS RESERVED
Please submit your comments or questions here, or contact Webmaster  ipmic@ipm.ir