Connected hyperplanes in binary matroids

Autor(es)

Lemos, Manoel ^[1] ; Melo, T. R. B. ^[1]

Afiliação do(s) autor(es)

^[1] Univ Fed Pernambuco, Dept Matemat, BR-50740540 Recife, PE - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Linear Algebra and its Applications; v. 432, n. 1, p. 259-274, JAN 1 2010.
• Citações Web of Science: 2

Resumo

For a 3-connected binary matroid M, let dim(A)(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where A subset of E(M). When A = empty set, Bixby and Cunningham, in 1979, showed that diM(A)(M) = r(M). In 2004, when vertical bar A vertical bar = 1, Lemos proved that dim(A) M = r(M) - 1. In this paper, we characterize the 3-connected binary matroids having a pair of elements that meets every non-separating cocircuit. Using this result, we show that 2 dim(A) (M) >= r(M) - 3, when M is regular and vertical bar A vertical bar = 2. For vertical bar A vertical bar = 3, we exhibit a family of cographic matroids with a 3-element set intersecting every non-separating cocircuit. We also construct the matroids that attains McNulty and Wu's bound for the number of non-separating cocircuits of a simple and cosimple connected binary matroid. (C) 2009 Elsevier Inc. All rights reserved. (AU)

• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático