| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4654105 | European Journal of Combinatorics | 2010 | 6 Pages |
Abstract
We study homomorphisms between randomly directed paths and give estimates on the probability of the existence of such a homomorphism. We show that a random path is a core with a positive probability. We apply our results in the investigation of homomorphism dualities, the most natural situation when a homomorphism (or Constraint Satisfaction) problem is in coNP.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Gábor Kun, Claude Tardif,