Lattices related to extensions of presentations of transversal matroids

Publication date 10 April 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.00870, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p49

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

distributive lattices presentations single-element extensions transversal matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Transversal (matching) theory (05D15) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: For a presentation

m a t h c a l A

of a transversal matroid

M

, we study the set

T_{m a t h c a l A}

of single-element transversal extensions of

M

that have presentations that extend

m a t h c a l A

; we order these extensions by the weak order. We show that

T_{m a t h c a l A}

is a distributive lattice, and that each finite distributive lattice is isomorphic to

T_{m a t h c a l A}

for some presentation

m a t h c a l A

of some transversal matroid

M

. We show that

T_{m a t h c a l A} c a p T_{m a t h c a l B}

, for any two presentations

m a t h c a l A

and

m a t h c a l B

of

M

, is a sublattice of both

T_{m a t h c a l A}

and

T_{m a t h c a l B}

. We prove sharp upper bounds on

| T_{m a t h c a l A} |

for presentations

m a t h c a l A

of rank less than

r (M)

in the order on presentations; we also give a sharp upper bound on

| T_{m a t h c a l A} c a p T_{m a t h c a l B} |

. The main tool we introduce to study

T_{m a t h c a l A}

is the lattice

L_{m a t h c a l A}

of closed sets of a certain closure operator on the lattice of subsets of

1, 2, l d o t s, r (M)

.

Review text

Summary: For a presentation \(\mathcal{A}\) of a transversal matroid \(M\), we study the ordered set \(T_{\mathcal{A}}\) of single-element transversal extensions of \(M\) that have presentations that extend \(\mathcal{A}\); extensions are ordered by the weak order.~ We show that \(T_{\mathcal{A}}\) is a distributive lattice, and that each finite distributive lattice is isomorphic to \(T_{\mathcal{A}}\) for some presentation \(\mathcal{A}\) of some transversal matroid \(M\). We show that \(T_{\mathcal{A}}\cap T_{\mathcal{B}}\), for any two presentations \(\mathcal{A}\) and \(\mathcal{B}\) of \(M\), is a sublattice of both \(T_{\mathcal{A}}\) and \(T_{\mathcal{B}}\). We prove sharp upper bounds on \(|T_{\mathcal{A}}|\) for presentations \(\mathcal{A}\) of rank less than \(r(M)\) in the order on presentations; we also give a sharp upper bound on \(|T_{\mathcal{A}}\cap T_{\mathcal{B}}|\). The main tool we introduce to study \(T_{\mathcal{A}}\) is the lattice~\(L_{\mathcal{A}}\) of closed sets of a certain closure operator on the lattice of subsets of \(\{1,2,\ldots,r(M)\}\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Lattices related to extensions of presentations of transversal matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521371)