Majority digraphs

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

Research output: Contribution to JournalArticleAcademicpeer-review

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
Pages (from-to)3701-3715
Number of pages15
JournalProceedings of the American Mathematical Society
Volume144
Issue number9
DOIs
Publication statusPublished - 2016

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

Cite this