Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A recurrence for bounds on dominating sets in k-majority tournaments"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A recurrence for bounds on dominating sets in k-majority tournaments. | A recurrence for bounds on dominating sets in k-majority tournaments Dror Fidler dror.fid@gmail.com Submitted Dec 3 2010 Accepted Aug 7 2011 Published Aug 19 2011 Mathematics Subject Classification 05C20 05C69 91B14 Abstract A k-majority tournament is realized by 2k 1 linear orders on the set of vertices where a vertex u dominates v if u precedes v in at least k of the orders. Various properties of such tournaments have been studied among them the problem of finding the size of a smallest dominating set. It is known that 2-majority tournaments are dominated by 3 vertices and that k-majority tournaments are dominated by O k log k vertices. However precise values are not known even for k 3. We establish new upper bounds for the size of a smallest dominating set in k-majority tournaments that considerably improve upon previous bounds for small k. In particular our result shows that 3-majority tournaments are dominated by at most 12 vertices. 1 Introduction A k-majority tournament is a finite tournament T V E which is realized by 2k 1 linear orders lists on the set of vertices. For every two vertices u v E V u v E E if and only if the index of u is smaller than the index of v in at least k of the lists. k-majority tournaments arise in social choice theory where each vertex may represent a candidate and the lists represent the ranking of the candidates by different voters. The connection between k-majority tournaments and general tournaments has been explored. The function k0 n denotes the least integer k such that every tournament with n vertices may be represented as a k-majority tournament by 2k 1 ordered lists on V. McGarvey 3 showed that k0 is well-defined for every n and Erdos and L. Moser 2 showed k0 n O n log n . A dominating set in T is a subset W c V such that for every vertex v E V W there exists a vertex u E W such that u v E E. It was first demonstrated in 2 that there exist tournaments whose smallest dominating set is arbitrarily large however somewhat .