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

Digraph
If and only if
Propositional Logic
Reversal
Assertion
Finite Set
Logic
Cycle

Cite this

Lai, Tri ; Endrullis, Jörg ; Moss, Lawrence S. / Majority digraphs. In: Proceedings of the American Mathematical Society. 2016 ; Vol. 144, No. 9. pp. 3701-3715.
@article{4718d78d67064ffdb79cb1c4fa07b5a2,
title = "Majority digraphs",
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.",
author = "Tri Lai and J{\"o}rg Endrullis and Moss, {Lawrence S.}",
year = "2016",
doi = "10.1090/proc/13038",
language = "English",
volume = "144",
pages = "3701--3715",
journal = "Proceedings of the American Mathematical Society",
issn = "0002-9939",
publisher = "American Mathematical Society",
number = "9",

}

Majority digraphs. / Lai, Tri; Endrullis, Jörg; Moss, Lawrence S.

In: Proceedings of the American Mathematical Society, Vol. 144, No. 9, 2016, p. 3701-3715.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Majority digraphs

AU - Lai, Tri

AU - Endrullis, Jörg

AU - Moss, Lawrence S.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84975166280&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84975166280&partnerID=8YFLogxK

U2 - 10.1090/proc/13038

DO - 10.1090/proc/13038

M3 - Article

VL - 144

SP - 3701

EP - 3715

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

SN - 0002-9939

IS - 9

ER -