pith. sign in

arxiv: 1906.10936 · v1 · pith:GTKEB45Mnew · submitted 2019-06-26 · 🧮 math.CO

Cyclic Flats of Binary Matroids

Ragnar Freij-Hollanti , Matthias Grezet , Camilla Hollanti , Thomas Westerb\"ack This is my paper

Pith reviewed 2026-05-25 15:45 UTC · model grok-4.3

classification 🧮 math.CO
keywords binary matroidscyclic flatsmatroid minorslattice of flatsatomic latticesmatroid characterization
0
0 comments X

The pith

Binary matroids are characterized by the structure of their cyclic flat lattices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines two natural maps sending the lattice of cyclic flats of a matroid to the lattice of cyclic flats of any of its minors. These maps are then used to prove that binary matroids can be recognized exactly by properties of this lattice. The same work establishes that the cyclic flat lattice of any simple binary matroid without isthmuses is atomic. A reader would care because the result gives a purely combinatorial test for whether a matroid arises from a matrix over the two-element field.

Core claim

Binary matroids are characterised via their lattice of cyclic flats. Two natural maps from the cyclic flat lattice of M to the lattice of cyclic flats of a minor of M are given. It is shown that the lattice of cyclic flats of a simple binary matroid without isthmuses is atomic.

What carries the argument

The lattice of cyclic flats Z(M) equipped with the two natural maps to the cyclic flat lattices of minors.

If this is right

  • Any matroid whose cyclic flat lattice satisfies the characterizing conditions must be binary.
  • The atomicity property holds for every simple binary matroid without isthmuses.
  • Two matroids with isomorphic cyclic flat lattices are either both binary or both non-binary.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The maps may extend to give similar lattice characterizations for matroids representable over other small finite fields.
  • Atomicity of the cyclic flat lattice may imply the absence of certain minor configurations beyond those already excluded by simplicity and lack of isthmuses.
  • Lattice-based recognition could be turned into a computational test for binariness once the characterizing lattice axioms are made fully explicit.

Load-bearing premise

The two natural maps from the cyclic flat lattice to the lattices of minors preserve enough structure to support a complete characterization of binary matroids.

What would settle it

A concrete matroid that is not binary yet has a cyclic flat lattice isomorphic to the lattice of some binary matroid.

Figures

Figures reproduced from arXiv: 1906.10936 by Camilla Hollanti, Matthias Grezet, Ragnar Freij-Hollanti, Thomas Westerb\"ack.

Figure 1
Figure 1. Figure 1: Illustration of Lemma 6. ρ(Y − a) < ρ(Y ). But since a /∈ cyc(Y ) and a /∈ X then X ∪ cyc(Y ) ⊆ Y − a. This implies that ρ(X ∪ cyc(Y )) ≤ ρ(Y − a) < ρ(Y ), which is a contradiction. The condition Y − X ⊆ cyc(Y ) is also sufficient to guarantee that Y − X ∈ Z(M|Y /X). This proves Condition 2. Finally, for every other cyclic flat of M, cl(X ∪cyc(Z ∩Y ))∩(Y − X) = ∅ if and only if cyc(Z ∩ Y ) ⊆ X. But since X… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of Definition 8 and Lemma 9 Dually, every cyclic flat that contains A also contains cl(A), so T Z⊇A Z∈Z(M) Z ⊇ cl(A). It then follows that A ∨ = cyc   \ Z⊇A Z∈Z(M) Z   ⊇ cyc(cl(A)). Finally, as A ⊆ cl(A) we have that cyc(A) ⊆ cyc(cl(A)), and as the latter is a flat by (1), we have cl(cyc(A)) ⊆ cyc(cl(A)) [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Lattice of cyclic flats of the matroid from Example 1. Proof. Since the minimum distance is greater than 1, this implies that M contains no isthmuses and 1Z = E. Now the minimum distance satisfies the relation d = η(E) + 1 − max{η(Z) : Z ∈ Z(M) such that Z ⋖ E}. Therefore, if Z ∈ Z(M) is such that Z ⋖ E, we have that 2 ≤ η(E) − η(Z) and the edge Z ⋖ E is a nullity edge. Avoiding a U 2 4 minor is not the on… view at source ↗
Figure 4
Figure 4. Figure 4: displays the lattice of cyclic flats of the binary (6, 3, 3)-matroid with generator matrix G =   1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1   . ∅ 124 135 256 346 ρ = 2 123456 ρ = 3 [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Lattice of cyclic flats of the binary (8, 4, 4)-matroid. We can now summarize the previous results. Theorem 14. Let M = (E, ρ) be a binary simple (n, k, d)-matroid with no isth￾muses. If Z(M) has height 3, then either η(E) = 2 or M is isomorphic to one of the matroids listed below: • The (6, 3, 3)-matroid with 4 atoms. • The (7, 3, 4)-matroid with 7 atoms. • The (7, 4, 3)-matroid with 7 atoms. • The (8, 4,… view at source ↗
Figure 6
Figure 6. Figure 6: Configuration of the lattice of cyclic flats of M∗ (K5). Finally, to prove the proposition, we link the minimum distance d to the mini￾mum distance of M/Z1. We have dM/Z1 = ηM/Z1 (E − Z1) + 1 − max{ηM/Z1 (Z˜) : Z˜ ∈ Z(M/Z1) − (E − Z1)} = η(E) − η(Z1) + 1 − max{η(Z − Z1) : Z ∈ Z(M) − E and Z1 ⊆ Z} = η(E) − η(Z1) + 1 − max{η(Z) : Z ∈ Z(M) − E and Z1 ⊆ Z} + η(Z1) = η(E) + 1 − η(Z d ) = d. Hence, by the classi… view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of the hypotheses in Lemma 26. (2) If |ΥZ2 | = 2 and E − ( S Z∈ΥZ2 Z) 6= ∅, then we have η(E) = 1 + X Z∈ΥZ2 η(Z) − η(Z2) ≤ 1 + 2η(Z d ) − η(Z c ) ⇐⇒ d ≤ 2 + (η(Z d ) − η(Z c )). (3) if |ΥZ2 | = 2 and E = S Z∈ΥZ2 Z, then we have η(E) = X Z∈ΥZ2 η(Z) − η(Z2) ≤ 2η(Z d ) − η(Z c ) ⇐⇒ d ≤ 1 + (η(Z d ) − η(Z c )). Hence, the general upper bound for d is the largest of the three bounds obtained above … view at source ↗
Figure 8
Figure 8. Figure 8: Lattice of cyclic flats of the binary (11, 4, 5)-matroid from Example 4. Corollary 10. For a binary (n, k, d)-matroid, we have n ≥ k X−1 i=0  d 2 i  . We start by the proof of Theorem 15. Proof. Let M = (E, ρ) be a binary (n, k, d)-matroid. We separate the proof into three cases in which we give an explicit construction of the set A with the required parameters. Notice that the covering relations of the … view at source ↗
read the original abstract

In this paper, first steps are taken towards characterising lattices of cyclic flats $\mathcal{Z}(M)$ that belong to matroids $M$ that can be represented over a prescribed finite field $\mathbb{F}_q$. Two natural maps from $\mathcal{Z}(M)$ to the lattice of cyclic flats of a minor of $M$ are given. Binary matroids are characterised via their lattice of cyclic flats. It is shown that the lattice of cyclic flats of a simple binary matroid without isthmuses is atomic.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper takes initial steps toward characterizing the cyclic flat lattices Z(M) of matroids representable over a finite field F_q. It introduces two natural maps from Z(M) to the cyclic flat lattice of a minor of M. Binary matroids are characterized via their lattices of cyclic flats, and it is shown that the cyclic flat lattice of a simple binary matroid without isthmuses is atomic.

Significance. If the maps are shown to be sufficiently structure-preserving, the characterization would supply a lattice-theoretic criterion for binary representability, complementing existing circuit and flat axioms. The atomicity theorem for simple binary matroids without isthmuses is a self-contained structural result that could be of independent interest in matroid theory.

major comments (2)
  1. [Abstract] Abstract and the section introducing the maps: the claim that binary matroids are characterised via Z(M) rests on the two natural maps from Z(M) to the cyclic flat lattice of a minor preserving enough order and join/meet structure to force GF(2)-representability. No explicit statement is given that the maps are injective on the relevant sublattices or that they reflect the circuit axioms distinguishing binary matroids; without this, the characterization does not follow from the lattice axioms alone.
  2. [Atomicity theorem] The atomicity result for simple binary matroids without isthmuses inherits the same map-based reasoning; the proof must verify that the maps preserve atomicity under deletion and contraction while excluding isthmuses, but the load-bearing step (how the maps interact with the absence of isthmuses) is not isolated as a separate lemma.
minor comments (2)
  1. Notation for the two maps is introduced without a uniform symbol; consistent naming (e.g., φ and ψ) would improve readability when they are applied repeatedly.
  2. [Abstract] The abstract states that 'characterizations and proofs exist' for the F_q case in general, but only the binary case is treated; a brief remark on why the binary case is handled first would clarify the scope.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and valuable comments. We address the two major comments below and will incorporate clarifications in the revised manuscript to strengthen the presentation of the maps and the atomicity proof.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the section introducing the maps: the claim that binary matroids are characterised via Z(M) rests on the two natural maps from Z(M) to the cyclic flat lattice of a minor of M preserving enough order and join/meet structure to force GF(2)-representability. No explicit statement is given that the maps are injective on the relevant sublattices or that they reflect the circuit axioms distinguishing binary matroids; without this, the characterization does not follow from the lattice axioms alone.

    Authors: The two maps are constructed precisely so that they preserve the order, joins, and meets needed to transfer the circuit axioms of binary matroids to the lattice setting. The characterization theorem then follows directly from this preservation. We agree, however, that the manuscript would benefit from an explicit statement confirming injectivity on the relevant sublattices and the reflection of the distinguishing circuit axioms. We will add this clarification in the section defining the maps and restate it in the characterization theorem. revision: yes

  2. Referee: [Atomicity theorem] The atomicity result for simple binary matroids without isthmuses inherits the same map-based reasoning; the proof must verify that the maps preserve atomicity under deletion and contraction while excluding isthmuses, but the load-bearing step (how the maps interact with the absence of isthmuses) is not isolated as a separate lemma.

    Authors: The proof already verifies that the maps preserve atomicity under deletion and contraction, with the absence of isthmuses ensuring that every atom in the lattice corresponds to a circuit of length at least three. We acknowledge that isolating the interaction between the maps and the no-isthmus hypothesis as a separate lemma would improve readability. We will extract this step into a dedicated lemma in the revised version. revision: yes

Circularity Check

0 steps flagged

Characterization via cyclic flat lattices and minor maps is presented directly without reduction to self-definition or fitted inputs.

full rationale

The paper introduces two natural maps from the cyclic flat lattice Z(M) to minors and uses them to characterize binary matroids, along with an atomicity result for simple binary matroids without isthmuses. No equations or definitions in the provided abstract or description reduce the claimed characterization to a tautology, fitted parameter, or self-citation chain; the maps are stated as given constructions supporting the result. This aligns with a minor self-citation tolerance (score 2) but shows no load-bearing circularity, as the derivation remains self-contained against the lattice axioms and minor operations without importing uniqueness from prior author work or renaming known results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Relies on the standard axioms and definitions of matroid theory and lattice theory; no free parameters, invented entities, or ad-hoc axioms are indicated in the abstract.

axioms (1)
  • standard math Standard axioms of matroid theory including flats, circuits, and minors
    The results build directly on established definitions in matroid theory.

pith-pipeline@v0.9.0 · 5609 in / 1101 out tokens · 27595 ms · 2026-05-25T15:45:16.638906+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Birkhoff, Lattice Theory, 3rd Edition, Vol

    G. Birkhoff, Lattice Theory, 3rd Edition, Vol. 25 of Collo quium Publications, American Mathematical Society, 1967

    work page 1967

  2. [2]

    J. A. Sims, Some problems in matroid theory, Ph.D. thesis , University of Oxford (1980)

    work page 1980

  3. [3]

    J. E. Bonin, A. de Mier, The lattice of cyclic flats of a matr oid, Annals of Combinatorics 12 (2) (2008) 155–170

    work page 2008

  4. [4]

    Prideaux, Matroids, cyclic flats, and polyhedra, Mast er’s thesis, Victoria University of W ellington (2016)

    K. Prideaux, Matroids, cyclic flats, and polyhedra, Mast er’s thesis, Victoria University of W ellington (2016)

    work page 2016

  5. [5]

    J. N. Eberhardt, Computing the Tutte polynomial of a matr oid from its lattice of cyclic flats, The Electronic Journal of Combinatorics 21 (3) (2014) 3–47

    work page 2014

  6. [6]

    W esterb¨ ack, R

    T. W esterb¨ ack, R. Freij-Hollanti, T. Ernvall, C. Holla nti, On the combinatorics of locally repairable codes via matroid theory, IEEE Transactions on I nformation Theory 62 (10) (2016) 5296–5315

    work page 2016

  7. [7]

    Rota, Combinatorial theory, old and new, in: Actes du Congr` es International des Math´ ematiciens (Nice, 1970), 1971, pp

    G.-C. Rota, Combinatorial theory, old and new, in: Actes du Congr` es International des Math´ ematiciens (Nice, 1970), 1971, pp. 229–233

    work page 1970

  8. [8]

    Geelen, B

    J. Geelen, B. Gerards, G. Whittle, Solving Rota’s conjec ture, Notices of the American Math- ematical Society 61 (7) (2014) 736–743

    work page 2014

  9. [9]

    Oxley, Matroid Theory, 2nd Edition, Vol

    J. Oxley, Matroid Theory, 2nd Edition, Vol. 21 of Oxford G raduate Texts in Mathematics, Oxford University Press, 2011

    work page 2011

  10. [10]

    D. S. Papailiopoulos, A. G. Dimakis, Locally repairabl e codes, in: Proceedings of the IEEE International Symposium on Information Theory, 2012, pp. 2 771–2775

    work page 2012

  11. [11]

    Silberstein, A

    N. Silberstein, A. Zeh, Anticode-based locally repair able codes with high availability, Designs, Codes and Cryptography 86 (2) (2018) 419–445

    work page 2018

  12. [12]

    Huang, E

    P. Huang, E. Yaakobi, H. Uchikawa, P. H. Siegel, Cyclic l inear binary locally repairable codes, in: Proceedings of the IEEE information theory workshop, IE EE, 2015, pp. 1–5

    work page 2015

  13. [13]

    W. C. Huffman, V. Pless, Fundamentals of Error-Correcti ng Codes, Cambridge University Press, 2010

    work page 2010

  14. [14]

    Grezet, R

    M. Grezet, R. Freij-Hollanti, T. W esterb¨ ack, C. Holla nti, On binary matroid minors and applications to data storage over small fields, in: Internat ional Castle Meeting on Coding Theory and Applications, 2017, pp. 139–153

    work page 2017

  15. [15]

    Grezet, R

    M. Grezet, R. Freij-Hollanti, T. W esterb¨ ack, O. Olmez , C. Hollanti, Bounds on binary lo- cally repairable codes tolerating multiple erasures, in: T he International Zurich Seminar on Information and Communication (IZS). Proceedings, Zurich , Switzerland, 2018, pp. 103–107

    work page 2018

  16. [16]

    V´ amos, The missing axiom of matroid theory is lost fo rever, Journal of the London Math- ematical Society 2 (3) (1978) 403–408

    P. V´ amos, The missing axiom of matroid theory is lost fo rever, Journal of the London Math- ematical Society 2 (3) (1978) 403–408. CYCLIC FLATS OF BINARY MATROIDS 37

    work page 1978

  17. [17]

    missing axio m

    D. Mayhew, M. Newman, G. Whittle, Yes, the “missing axio m” of matroid theory is lost forever, Transactions of the American Mathematical Societ y 370 (8) (2018) 5907–5929

    work page 2018

  18. [18]

    W. T. Tutte, A homotopy theorem for matroids, I, II, Tran sactions of the American Mathe- matical Society 88 (1) (1958) 144–174

    work page 1958

  19. [19]

    Segre, Curve razionali normali e k-archi negli spazi finiti, Annali di Matematica Pura ed Applicata 39 (1) (1955) 357–379

    B. Segre, Curve razionali normali e k-archi negli spazi finiti, Annali di Matematica Pura ed Applicata 39 (1) (1955) 357–379

    work page 1955

  20. [20]

    Ball, On sets of vectors of a finite vector space in whic h every subset of basis size is a basis, Journal of the European Mathematical Society 14 (3) (2012) 7 33–748

    S. Ball, On sets of vectors of a finite vector space in whic h every subset of basis size is a basis, Journal of the European Mathematical Society 14 (3) (2012) 7 33–748

    work page 2012

  21. [21]

    H. H. Crapo, G.-C. Rota, On the Foundations of Combinato rial Theory: Combinatorial Geometries, MIT Press, 1970

    work page 1970

  22. [22]

    R. P. Stanley, Enumerative Combinatorics, 2nd Edition , Vol. 1, Cambridge University Press, 2011

    work page 2011

  23. [23]

    Shoda, Large families of matroids with the same Tutte polynomial, Ph.D

    K. Shoda, Large families of matroids with the same Tutte polynomial, Ph.D. thesis, George W ashington University (2012). (Freij-Hollanti, Grezet and Hollanti) Department of Mathematics and Systems Analysis, Aalto University, FI-00076 Aalto, Finland (W esterb¨ ack)Division of Applied Mathematics, UKK, M ¨alardalen University, H ¨ogskoleplan 1, Box 883, 721...

    work page 2012