Published May 30, 2011
| Version Published
Journal Article
Open
The quantifier semigroup for bipartite graphs
Creators
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.
Additional Information
© 2011 The Author(s). Submitted: Jun 22, 2010; Accepted: May 17, 2011; Published: May 30, 2011. Supported in part by NSF CCR-0326554, NSF CCF-0515342, NSA H98230-06-1-0074, and NSF CCF-0829909. Thanks to an anonymous referee for helpful comments on the paper.Attached Files
Published - Schulman2011p14143Electron_J_Comb.pdf
Files
Schulman2011p14143Electron_J_Comb.pdf
Additional details
Identifiers
- Eprint ID
- 24053
- Resolver ID
- CaltechAUTHORS:20110620-085724958
Funding
- NSF
- CCR-0326554
- NSF
- CCF-0515342
- NSF
- CCF-0829909
- National Security Agency
- H98230-06-1-0074
Dates
- Created
-
2011-06-20Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field