Vol. 5, No. 1, 2012

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 4, 543–722
Issue 3, 363–541
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Editors' interests
 
Subscriptions
 
ISSN 1944-4184 (online)
ISSN 1944-4176 (print)
 
Author index
To appear
 
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 Kn.

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/