TAILIEUCHUNG - Báo cáo khoa học:Transversal and cotransversal matroids via their representations

This note gives a new proof of the theorem, due to Ingleton and Pi [3], that the duals of transversal matroids are precisely the strict gammoids. Section 1 denes the relevant objects. Section 2 presents explicit representations of the families of transversal matroids and strict gammoids. Section 3 uses these representations to prove the duality of these two families. | Transversal and cotransversal matroids via their representations. Federico Ardila Submitted May 23 2006 Accepted Feb 27 2007 Published Mar 5 2007 Mathematics Subject Classification 05B35 05C38 05A99 Abstract. It is known that the duals of transversal matroids are precisely the strict gammoids. We show that by representing these two families of matroids geometrically one obtains a simple proof of their duality. 0 This note gives a new proof of the theorem due to Ingleton and Piff 3 that the duals of transversal matroids are precisely the strict gammoids. Section 1 defines the relevant objects. Section 2 presents explicit representations of the families of transversal matroids and strict gammoids. Section 3 uses these representations to prove the duality of these two families. 1 Matroids and duality. A matroid M E B is a finite set E together with a non-empty collection B of subsets of E called the bases of M which satisfy the following axiom If B1 B2 are bases and e is in B1 B2 there exists f in B2 B1 such that B1 e u f is a basis. If M E B is a matroid then B fE B I B 2 Bg is also the collection of bases of a matroid M E B called the dual of M. Representable matroids. Matroids can be thought of as providing a combinatorial abstraction of linear independence. If V is a set of vectors in a vector space and B is the federico@. Dept. of Mathematics San Francisco State University San Francisco CA USA. Supported by NSF grant DMS-9983797. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 N6 1 collection of maximal linearly independent subsets of V then M V B is a matroid. Such a matroid is called representable and V is called a representation of M. Transversal matroids. Let A1 . Ar be subsets of n 1 . ng. A transversal or system of distinct representatives of A1 . Ar is an r-subset of n whose elements can be labelled e1 . er in such a way that ei is in Ai for each i. The transversals of A1 . Ar are the bases of a matroid on n . Such a matroid is called a .

• Báo cáo khoa học
• representations
• Transversal
• cotransversal matroids
• representations strict gammoids
• transversal matroids
• scientific reports
• scientific research
• Communications in Physics
• On the coherent state method
• Constructing representations of quantum superalgebras
• The biggest quantum superalgebra representations
• Superalgebras and quantum superalgebras
• Mathematics
• Physics
• scientific studies
• natural sciences
• Improving Word Representations
• Global Context
• Multiple Word Prototypes
• Eric H
• Huang
• Richard Socher
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Word representations
• A simple and general method
• semi supervised learning
• Contextualizing Semantic Representations
• Syntactically Enriched Vector Models
• Stefan Thater and Hagen Fürstenau and Manfred Pinkal
• From Bilingual Dictionaries
• Interlingual Document Representations
• Jagadeesh Jagarlamudi
• Learning Condensed Feature Representations
• Large Unsupervised Data Sets
• Supervised Learning
• Distributional Representations
• Handling Sparsity
• Supervised Sequence Labeling
• xử lý ngôn ngữ tự nhiên
• Task oriented Evaluation
• Syntactic Parsers
• Their Representations
• An Improved Redundancy Elimination Algorithm
• Underspecified Representations
• Alexander Koller and Stefan Thater
• mô hình ngôn ngữ
• Mapping between Compositional Semantic Representations
• Lexical Semantic Resources
• Towards Accurate Deep Semantic Parsing
• Efficient Processing
• Underspecified Discourse Representations
• Michaela Regneri
• Finding Ideographic Representations
• Japanese Names Written in Latin Script
• Yan Qu Clairvoyance
• Language Identification
• Corpus Validation
• Ambiguity Preserving Machine Translation
• Packed Representations
• Long Papers
• Parsing Parallel Grammatical
• Derrick Higgins
• Automatic Construction
• Frame Representations
• Spont aneous Speech in Unrestricted Domains
• Syntagmatic
• Paradigmatic Representations
• Term Variation
• COMPACT REPRESENTATIONS
• FINITE STATE TRANSDUCERS
• Head Automata
• Bilingual Tiling
• Translation with Minimal Representations
• Acquisition of a Lexicon
• Semantic Representations of Sentences
• Cynthia A
• Thompson
• ASIMPLIFIED THEORY
• TENSE REPRESENTATIONS
• CONSTRAINTS ON THEIR COMPOSITION
• model language
• process natural language
• A Logic of Semantic Representations
• Shallow Parsing
• Alexander Koller
• Integrating Symbolic
• Statistical Representations
• The Lexicon Pragmatics Interface
• Tree Representations
• Probabilistic Models
• Extended Named Entities Detection