Betti numbers of order-preserving graph homomorphisms

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

Milestones

Received: 27 May 2011

Accepted: 11 July 2011

Published: 28 April 2012

Communicated by Jim Haglund

Authors

Lauren Guerra
Mathematical Sciences Building One Shields Ave. University of California Davis, CA 95616 United States

Steven Klee
Mathematical Sciences Building One Shields Ave. University of California Davis, CA 95616 United States
http://www.math.ucdavis.edu/~klee/

Vol. 5, No. 1, 2012

Lauren Guerra and Steven Klee

Abstract

Keywords

Mathematical Subject Classification 2010

Milestones

Authors