Powerful sets: a generalisation of binary matroids

Graham E. Farr, Andrew Y.Z. Wang

Research output: Contribution to journalArticleResearchpeer-review

Abstract

A set S ⊆ {0, 1}E of binary vectors, with positions indexed by E, is said to be a powerful code if, for all X ⊆ E, 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 S ⊆ 2E of subsets of E is a 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 F2), 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.

Original languageEnglish
Article number#P3.42
Pages (from-to)1-20
Number of pages20
JournalThe Electronic Journal of Combinatorics
Volume25
Issue number3
Publication statusPublished - 7 Sep 2018

Keywords

  • Matroid
  • Powerful code
  • Powerful set
  • Rank function

Cite this

@article{dbadeb94bee14d4ea0480aaf3f29cac6,
title = "Powerful sets: a generalisation of binary matroids",
abstract = "A set S ⊆ {0, 1}E of binary vectors, with positions indexed by E, is said to be a powerful code if, for all X ⊆ E, 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 S ⊆ 2E of subsets of E is a 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 F2), 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.",
keywords = "Matroid, Powerful code, Powerful set, Rank function",
author = "Farr, {Graham E.} and Wang, {Andrew Y.Z.}",
year = "2018",
month = "9",
day = "7",
language = "English",
volume = "25",
pages = "1--20",
journal = "The Electronic Journal of Combinatorics",
issn = "1077-8926",
publisher = "Clemson University Digital Press",
number = "3",

}

Powerful sets : a generalisation of binary matroids. / Farr, Graham E.; Wang, Andrew Y.Z.

In: The Electronic Journal of Combinatorics, Vol. 25, No. 3, #P3.42, 07.09.2018, p. 1-20.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Powerful sets

T2 - a generalisation of binary matroids

AU - Farr, Graham E.

AU - Wang, Andrew Y.Z.

PY - 2018/9/7

Y1 - 2018/9/7

N2 - A set S ⊆ {0, 1}E of binary vectors, with positions indexed by E, is said to be a powerful code if, for all X ⊆ E, 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 S ⊆ 2E of subsets of E is a 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 F2), 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.

AB - A set S ⊆ {0, 1}E of binary vectors, with positions indexed by E, is said to be a powerful code if, for all X ⊆ E, 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 S ⊆ 2E of subsets of E is a 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 F2), 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.

KW - Matroid

KW - Powerful code

KW - Powerful set

KW - Rank function

UR - http://www.scopus.com/inward/record.url?scp=85053255076&partnerID=8YFLogxK

M3 - Article

VL - 25

SP - 1

EP - 20

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

IS - 3

M1 - #P3.42

ER -