2015/09/24 by Tri Lai, Lai, Tri, Jörg Endrullis +3
Computer Science · Mathematics · #03B65 #05C62 #Advanced Algebra and Logic #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #math.CO #math.LO #msc:03B65 #msc:05C62 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1509.07567
15 pages, 2 figures
arxiv created 2015/09/24 · openalex publication_date 2015/09/24 · arxiv updated 2015/09/28 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
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 |Au ∩ Av | > (1)/(2) ⋅ |Au|. We characterize the majority digraphs as the digraphs with the property that every directed cycle has a reversal. If we change (1)/(2) 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.