Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Majority Digraphs


Authors: Tri Lai, Jörg Endrullis and Lawrence S. Moss
Journal: Proc. Amer. Math. Soc. 144 (2016), 3701-3715
MSC (2010): Primary 05C62, 03B65
DOI: https://doi.org/10.1090/proc/13038
Published electronically: March 25, 2016
MathSciNet review: 3513532
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A majority digraph is a finite simple digraph $ G=(V,\to )$ such that there exist finite sets $ A_v$ for the vertices $ v\in V$ with the following property: $ u\to v$ if and only if ``more than half of the $ A_u$ are $ A_v$''. That is, $ u\to v$ if and only if $ \vert A_u \cap A_v \vert > \frac {1}{2} \cdot \vert A_u\vert$. We characterize the majority digraphs as the digraphs with the property that every directed cycle has a reversal. If we change $ \frac {1}{2}$ to any real number $ \alpha \in (0,1)$, we obtain the same class of digraphs. We apply the characterization result to obtain a result on the logic of assertions ``most $ X$ are $ Y$'' and the standard connectives of propositional logic.


References [Enhancements On Off] (What's this?)

  • [EM] Jörg Endrullis and Lawrence S. Moss, Syllogistic Logic with ``Most'', in V. de Paiva et al (eds.) Proceedings, Workshop on Logic, Language, Information and Computation (WoLLIC'15), 2015, 215-229.
  • [U] Chloe Urbanski, personal communication, 2013.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C62, 03B65

Retrieve articles in all journals with MSC (2010): 05C62, 03B65


Additional Information

Tri Lai
Affiliation: Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, Minnesota 55455
Email: tmlai@ima.umn.edu

Jörg Endrullis
Affiliation: Vrije Universiteit Amsterdam, 1081 HV Amsterdam, The Netherlands — and — Department of Mathematics, Indiana University, Bloomington, Indiana 47405
Email: j.endrullis@vu.nl

Lawrence S. Moss
Affiliation: Department of Mathematics, Indiana University, Bloomington, Indiana 47405
Email: lsm@cs.indiana.edu

DOI: https://doi.org/10.1090/proc/13038
Received by editor(s): August 29, 2014
Received by editor(s) in revised form: March 11, 2015, September 20, 2015, and November 16, 2015
Published electronically: March 25, 2016
Additional Notes: This work was partially supported by a grant from the Simons Foundation (#245591 to the third author).
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society