TAILIEUCHUNG - Báo cáo toán học: "Short certificates for 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í toán học quốc tế đề tài: Short certificates for tournaments. | Short certificates for tournaments Noga Alon Miklos Ruszinko y Submitted November 6 1996 Accepted March 13 1997. Abstract An isomorphism certificate of a labeled tournament T is a labeled subdigraph of T which together with an unlabeled copy of T allows the errorless reconstruction of T. It is shown that any tournament on n vertices contains an isomorphism certificate with at most n log2 n edges. This answers a question of Fishburn Kim and Tetali. A score certificate of T is a labeled subdigraph of T which together with the score sequence of T allows its errorless reconstruction. It is shown that there is an absolute constant e 0 so that any tournament on n vertices contains a score certificate with at most 1 2 e n2 edges. 1 Introduction A tournament is an oriented complete graph. An isomorphism certificate of a labeled tournament T is a labeled subdigraph D of T which together with an unlabeled copy of T allows the errorless reconstruction of T. More precisely if V v1 . vng denotes the vertex set of T then a subdigraph D of T is such a certificate if for any tournament T on V which is isomorphic to T and contains D T is in fact identical to T. The size of the certificate D is the number of its edges and D is a minimum certificate if no isomorphism certificate has a smaller size. Note that the unique directed Hamilton path in a transitive tournament on n vertices is an isomorphism certificate of size n 1 for the tournament. It is also not difficult to check that any edge Department of Mathematics Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv University Ramat Aviv Tel Aviv Israel. Email noga@. Research Supported in part by a USA Israeli BSF grant. Computer and Automation Research Institute of the Hungarian Academy of Sciences Budapest 63 Hungary-1518. Email ruszinko@. Research supported in part by OTKA Grants T 016414 and W 015796 and the Magyar Tudományért Foundation. 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 4

• Báo cáo khoa học
• 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
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội