THE COCYCLE LATTICE OF BINARY MATROIDS

被引：8
|
作者：
LOVASZ, L
SERESS, A
机构：
[1] EOTVOS LORAND UNIV, H-1088 BUDAPEST, HUNGARY
[2] OHIO STATE UNIV, COLUMBUS, OH 43210 USA
[3] PRINCETON UNIV, PRINCETON, NJ 08544 USA
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 1993年 / 14卷 / 03期
关键词：
D O I：
10.1006/eujc.1993.1027
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We study the lattice (grid) generated by the incidence vectors of cocycles of a binary matroid and its dual lattice. We characterize those binary matroids for which the obvious characterization yields a polynomial time algorithm to check whether a matroid has this property, and also to construct a basis in the cocycle lattice. For the general case, we prove that every denominator in the dual lattice is a power of 2, and derive upper and lower bounds for the largest exponent. © 1993 Academic Press, Inc.
引用
收藏
页码：241 / 250
页数：10
相关论文
共 50 条
  • [31] Binary matroids that classify forests
    Traldi, L.
    ALGEBRA AND DISCRETE MATHEMATICS, 2022, 33 (02): : 128 - 150
  • [32] On the impossibility of decomposing binary matroids
    Leichter, Marilena
    Moseley, Benjamin
    Pruhs, Kirk
    OPERATIONS RESEARCH LETTERS, 2022, 50 (05) : 623 - 625
  • [33] Binary matroids and local complementation
    Traldi, Lorenzo
    EUROPEAN JOURNAL OF COMBINATORICS, 2015, 45 : 21 - 40
  • [34] Lattice Path Bicircular Matroids
    Santiago Guzmán-Pro
    Winfried Hochstättler
    Graphs and Combinatorics, 2024, 40
  • [35] CIRCUIT BASIS IN BINARY MATROIDS
    LONGYEAR, JQ
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1973, 20 (06): : A563 - A563
  • [36] CIRCUIT DECOMPOSITIONS OF BINARY MATROIDS
    Frederickson, Bryce
    Michel, Lukas
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (02) : 1193 - 1201
  • [37] Splitting Lemma for Binary Matroids
    Shikare, M. M.
    SOUTHEAST ASIAN BULLETIN OF MATHEMATICS, 2008, 32 (01) : 151 - 159
  • [38] CHARACTERIZING BINARY SIMPLICIAL MATROIDS
    TODD, MJ
    DISCRETE MATHEMATICS, 1976, 6 (01) : 61 - 70
  • [39] Cyclic flats of binary matroids
    Freij-Hollanti, Ragnar
    Grezet, Matthias
    Hollanti, Camilla
    Westerback, Thomas
    ADVANCES IN APPLIED MATHEMATICS, 2021, 127
  • [40] Removable circuits in binary matroids
    Goddyn, LA
    Jackson, B
    COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (06): : 539 - 545
12345