tailieunhanh - Báo cáo toán học: "Acyclic 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: Acyclic sets in k-majority tournaments. | Acyclic sets in k-majority tournaments Kevin G. Milans Daniel H. Schreiber Douglas B. West Submitted Jul 31 2010 Accepted May 18 2011 Published May 30 2011 Mathematics Subject Classification 05C20 06A05 Abstract When n is a set of k linear orders on a ground set X and k is odd the k-majority tournament generated by n has vertex set X and has an edge from u to v if and only if a majority of the orders in n rank u before v. Let fk n be the minimum over all k-majority tournaments with n vertices of the maximum order of an induced transitive subtournament. We prove that f3 n n always and that f3 n 2 n 1 when n is a perfect square. We also prove that f5 n n1 4. For general k we prove that nck fk n ndk n where Ck 3- k-1 2 and 1 lg lg k dk n -1 lg k as n TO- 1 Introduction When n is a set of linear orders on a ground set X the majority digraph of n has vertex set X and has an edge from u to v if and only if a majority of the orders in n rank u before v. When n has size k and k is odd the majority digraph is a k-majority tournament. A k-majority tournament is a model of the consensus preferences of a group of k individuals. In studying generalized voting paradoxes McGarvey 8 showed that every n-vertex tournament is realizable as a k-majority tournament with k 2 n . Erdos and Moser 6 improved this by showing that k O n log n always suffices and Stearns 9 showed that k Q n log n is sometimes necessary. In addition to modeling group preferences using a small number of criteria the k-majority tournaments for fixed k form a well-behaved class of tournaments. For example consider domination. The domination number of a directed graph D denoted Y D is the minimum size of a vertex subset S such that each vertex not in S has an immediate Department of Mathematics University of South Carolina Columbia SC 29208 mi-lans@. Research supported by the National Science Foundation grant DMS 08-38434 EMSW21-MCTP Research Experience for Graduate Students . Daniel Schreiber .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học