2003/03/26 by Saharon Shelah, Shelah, Saharon
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #math.CO #math.LO
paper · pdf · doi:10.48550/arxiv.math/0303323
arxiv created 2003/03/26 · arxiv updated 2009/11/30
The main result is the following: Let X be a finite set and D be a non empty family of choice functions for (X choose 2) closed under permutation of X. Then the following conditions are equivalent: (A) for any choice function c on (X choose 2) we can find a finite set J and cj in D for j in J such that for any x not= y in X : cx,y=y Leftrightarrow |J|/2<| j in J:cjx,y= y| (so equality never occurs) (B) for some c in D and x in X we have |y: cx,y=y| not= (|X|-1)/2 . We then describe what is the closure of a set of choice functions by majority; in fact, there are just two possibilities (in section 3). In section 4 we discuss a generalization.