TAILIEUCHUNG - Báo cáo toán học: " Local equivalence of transversals in matroids"

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: Local equivalence of transversals in matroids. | Local equivalence of transversals in matroids D. Fon-Der-Flaass Mathematics Department Queen Mary and Westfield College London E1 4NS email Submitted May 21 1996 Accepted August 2 1996. Abstract Given any system of n subsets in a matroid M a transversal of this system is an n-tuple of elements of M one from each set which is independent. Two transversals differing by exactly one element are adjacent and two transversals connected by a sequence of adjacencies are locally equivalent the distance between them being the minimum number of adjacencies in such a sequence. We give two sufficient conditions for all transversals of a set system to be locally equivalent. Also we propose a conjecture that the distance between any two locally equivalent transversals can be bounded by a function of n only and provide an example showing that such function if it exists must grow at least exponentially. Let M be a matroid and V V1 . Vn a collection of subsets of M. By a transversal of V we mean a sequence v1 . vn of elements of M such that V 2 V for i 1 . n and v1 . vn are independent. By the well-known Rado s Theorem transversals exist if and only if the following condition is satisfied For every X c 1 . ng rank V X . 1 We say that a transversal vi . v n is a result of a local replacement of v1 . vn at i if v j Vj for j i and call two transversals locally equivalent if one can be obtained from the other by a sequence of local replacements the length of the shortest such sequence being the distance between the transversals. In this note we address two questions under what conditions are all transversals of a collection V locally equivalent and how big in terms of n can be the distance between two locally equivalent transversals. Also we shall consider in more detail the case when M is the free matroid the matroid having no cycles . On leave from Institute of Mathematics Novosibirsk Russia partially supported by the grant 96-01-01614 of the Russian Foundation .

• 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