Majority digraphs

Tri Lai, Jörg Endrullis, Lawrence S. Moss

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

A majority digraph is a finite simple digraph G = (V,→) such that there exist finite sets Av for the vertices v ∈ V with the following property: u → v if and only if “more than half of the Au are Av”. That is, u → v if and only if (formula presented). 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 α ∈ (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.

Original languageEnglish (US)
Pages (from-to)3701-3715
Number of pages15
JournalProceedings of the American Mathematical Society
Volume144
Issue number9
DOIs
StatePublished - 2016

Bibliographical note

Funding Information:
This work was partially supported by a grant from the Simons Foundation (#245591 to the third author).

Fingerprint Dive into the research topics of 'Majority digraphs'. Together they form a unique fingerprint.

Cite this