Vol. 5, No. 1, 2012
Download this article
Download this article For screen
For printing
Recent Issues

Volume 13
Issue 2, 181–360
Issue 1, 1–180

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
Editorial Board
Subscriptions
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Author Index
Coming Soon
 
Other MSP Journals
Betti numbers of order-preserving graph homomorphisms

Lauren Guerra and Steven Klee

Vol. 5 (2012), No. 1, 67–80
DOI: 10.2140/involve.2012.5.67
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/