Majority digraphs

Abstract: A majority digraph is a finite simple digraph

G = (V, o)

such that there exist finite sets

A_{v}

for the vertices

v i n V

with the following property:

u o v

if and only if "more than half of the

A_{u}

are

A_{v}

". That is,

u o v

if and only if

| A_{u} c a p A_{v} | > f r a c 12 c d o t | A_{u} |

. We characterize the majority digraphs as the digraphs with the property that every directed cycle has a reversal. If we change

f r a c 12

to any real number

a l p h a i n (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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Majority digraphs