๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Matroid Generalization of a Result on Row-Latin Rectangles

โœ Scribed by Glenn G. Chappell

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
194 KB
Volume
88
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let A be an m_n matrix in which the entries of each row are all distinct. A. A. Drisko (1998, J. Combin. Theory Ser. A 84, 181 195) showed that if m 2n&1, then A has a transversal: a set of n distinct entries with no two in the same row or column. We generalize this to matrices with entries in the ground set of a matroid. For such a matrix A, we show that if each row of A forms an independent set, then we can require the transversal to be independent as well. We determine the complexity of an algorithm based on the proof of this result. Finally, we observe that m 2n&1 appears to force the existence of not merely one but many transversals. We discuss a number of conjectures related to this observation (some of which involve matroids and some of which do not).

๐Ÿ“œ SIMILAR VOLUMES

A Note on the Asymptotic Number of Latin
A Note on the Asymptotic Number of Latin Rectangles
โœ I. Skau ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 75 KB

The enumeration problem of Latin rectangles is formulated in terms of permanents, and two 'hard' inequalities of permanents are applied in a squeezing manner, both giving and suggesting asymptotic formulas.

A generalization of a result of Tran Van
A generalization of a result of Tran Van Trung on t-designs
โœ Benoรฎt Baudelet; Michel Sebille ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 411 KB

We prove that if there exists a t -(v, k, ฮป) design satisfying the inequality for some positive integer j (where m = min{j, v -k} and n = min{i, t}), then there exists a t -(v + j, k, ฮป( v-t+j j )) design.

A Result on Spreads of the Generalized Q
A Result on Spreads of the Generalized QuadrangleT2(O), withOan Oval Arising from a Flock, and Applications
โœ J.A. Thas ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 114 KB

If F is a flock of the quadratic cone K of PG(3, q), q even, then the corresponding generalized quadrangle S(F) of order (q 2 , q) has subquadrangles T 2 (O), with O an oval, of order q. We prove in a geometrical way that any such T 2 (O) has spreads S consisting of an element y โˆˆ O and the q 2 line