#### Vol. 5, No. 1, 2012

 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login Author Index Coming Soon Contacts ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Other MSP Journals
Betti numbers of order-preserving graph homomorphisms

### Lauren Guerra and Steven Klee

Vol. 5 (2012), No. 1, 67–80
##### Abstract

For graphs $G$ and $H$ with totally ordered vertex sets, a function mapping the vertex set of $G$ to the vertex set of $H$ is an order-preserving homomorphism from $G$ to $H$ if it is nondecreasing on the vertex set of $G$ and maps edges of $G$ to edges of $H$. In this paper, we study order-preserving homomorphisms whose target graph $H$ is the complete graph on $n$ vertices. By studying a family of graphs called nonnesting arc diagrams, we are able to count the number of order-preserving homomorphisms (and more generally the number of order-preserving multihomomorphisms) mapping any fixed graph $G$ to the complete graph ${K}_{n}$.

##### Keywords
graph homomorphisms, Betti numbers, nonnesting partitions
##### Mathematical Subject Classification 2010
Primary: 13D02
Secondary: 05A18, 06A06, 05C30