“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| 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
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 | |||||
