Powerful sets: a generalisation of binary matroids

MaRDI QIDQ1671667zbMATH OpenFDO

Authors Graham Farr, Andrew Y. Z. Wang

Publication date 7 September 2018

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

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

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

matroidrank functionpowerful codepowerful set

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Linear codes (general theory) (94B05) Other types of codes (94B60) Designs and configurations (05B99)

Abstract: A set $Ssubseteq{0,1}^E$ of binary vectors, with positions indexed by $E$, is said to be a extit{powerful code} if, for all $XsubseteqE$, the number of vectors in $S$ that are zero in the positions indexed by $X$ is a power of 2. By treating binary vectors as characteristic vectors of subsets of $E$, we say that a set $Ssubseteq{2}^E$ of subsets of $E$ is a extit{powerful set} if the set of characteristic vectors of sets in $S$ is a powerful code. Powerful sets (codes) include cocircuit spaces of binary matroids (equivalently, linear codes over $mathbb{F}_2$), but much more besides. Our motivation is that, to each powerful set, there is an associated nonnegative-integer-valued rank function (by a construction of Farr), although it does not in general satisfy all the matroid rank axioms. In this paper we investigate the combinatorial properties of powerful sets. We prove fundamental results on special elements (loops, coloops, frames, near-frames, and stars), their associated types of single-element extensions, various ways of combining powerful sets to get new ones, and constructions of nonlinear powerful sets. We show that every powerful set is determined by its clutter of minimal nonzero members. Finally, we show that the number of powerful sets is doubly exponential, and hence that almost all powerful sets are nonlinear.

Recommendations

• Eigensets and power products of a bimatroid
• On sums which are powers
• On binary \(k\)-paving matroids and Reed-Muller codes
• Combinatorial properties of some classes of matrices over GF(2)
• Characterizations of finitary and cofinitary binary matroids

Cites work

• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• A generalization of the Whitney rank generating function
• Almost affine codes
• Arrangements, channel assignments, and associated polynomials
• On the Combinatorics of Locally Repairable Codes via Matroid Theory
• On the classification of ideal secret sharing schemes
• Some results on generalised Whitney functions
• The Redei function of a relation
• Tutte-Whitney polynomials: some history and generalizations

Cited in

(2)

• Binary functions, degeneracy, and alternating dimaps
• scientific article; zbMATH DE number 4179389 (Why is no real title available?)

This page was built for publication: Powerful sets: a generalisation of binary matroids

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