Betti numbers of order-preserving graph homomorphisms

Guerra, Lauren; Klee, Steven

doi:10.2140/involve.2012.5.67

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

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 $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