The Quantifier Semigroup for Bipartite Graphs

  • Leonard J. Schulman
DOI: https://doi.org/10.37236/610

Abstract

In a bipartite graph there are two widely encountered monotone mappings from subsets of one side of the graph to subsets of the other side: one corresponds to the quantifier "there exists a neighbor in the subset" and the other to the quantifier "all neighbors are in the subset." These mappings generate a partially ordered semigroup which we characterize in terms of "run-unimodal" words.

Published
2011-05-30
Issue
Volume 18, Issue 1 (2011)
Article Number
P123