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 such that there exist finite sets
for the vertices
with the following property:
if and only if ``more than half of the
are
''. That is,
if and only if
. We characterize the majority digraphs as the digraphs with the property that every directed cycle has a reversal. If we change
to any real number
, we obtain the same class of digraphs. We apply the characterization result to obtain a result on the logic of assertions ``most
are
'' and the standard connectives of propositional logic.
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