On a generalization of spikes

Nick Brettell; Rutger Campbell; Deborah Chun; Kevin Grace; Geoff Whittle

doi:10.1137/18M1182255

On a generalization of spikes

Nick Brettell
, Rutger Campbell
, Deborah Chun
, Kevin Grace
, Geoff Whittle

Discrete Mathematics

Research output: Contribution to journal › Article › Academic › peer-review

3 Citations (Scopus)

119 Downloads (Pure)

Abstract

We consider matroids with the property that every subset of the ground set of size t is contained in both an ℓ-element circuit and an ℓ-element cocircuit; we say that such a matroid has the (t, ℓ)-property. We show that for any positive integer t, there is a finite number of matroids with the (t, ℓ)-property for ℓ < 2t; however, matroids with the (t, 2t)-property form an infinite family. We say a matroid is a t-spike if there is a partition of the ground set into pairs such that the union of any t pairs is a circuit and a cocircuit. Our main result is that if a sufficiently large matroid has the (t, 2t)-property, then it is a t-spike. Finally, we present some properties of t-spikes.

Original language	English
Pages (from-to)	358-372
Number of pages	15
Journal	SIAM Journal on Discrete Mathematics
Volume	33
Issue number	1
DOIs	https://doi.org/10.1137/18M1182255
Publication status	Published - 1 Jan 2019

Funding

The first and fifth authors were supported by the New Zealand Marsden Fund. The second author was supported by NSERC Scholarship PGSD3-489418-2016. The fourth author was supported by National Science Foundation grant 1500343. The authors would like to thank the Mathematical Research Institute (MATRIX), Creswick, Victoria, Australia, for support and hospitality during the Tutte Centenary Retreat, 26 Nov.–2 Dec. 2017, where work on this paper was initiated.

Keywords

Circuit
Cocircuit
Matroid
Spike

Access to Document

10.1137/18M1182255

publishers versionFinal published version, 355 KB

Cite this

@article{dcd5fdb8a25d4d6bbefd2aaf28624e55,

title = "On a generalization of spikes",

abstract = "We consider matroids with the property that every subset of the ground set of size t is contained in both an ℓ-element circuit and an ℓ-element cocircuit; we say that such a matroid has the (t, ℓ)-property. We show that for any positive integer t, there is a finite number of matroids with the (t, ℓ)-property for ℓ < 2t; however, matroids with the (t, 2t)-property form an infinite family. We say a matroid is a t-spike if there is a partition of the ground set into pairs such that the union of any t pairs is a circuit and a cocircuit. Our main result is that if a sufficiently large matroid has the (t, 2t)-property, then it is a t-spike. Finally, we present some properties of t-spikes.",

keywords = "Circuit, Cocircuit, Matroid, Spike",

author = "Nick Brettell and Rutger Campbell and Deborah Chun and Kevin Grace and Geoff Whittle",

year = "2019",

month = jan,

day = "1",

doi = "10.1137/18M1182255",

language = "English",

volume = "33",

pages = "358--372",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "1",

}

TY - JOUR

T1 - On a generalization of spikes

AU - Brettell, Nick

AU - Campbell, Rutger

AU - Chun, Deborah

AU - Grace, Kevin

AU - Whittle, Geoff

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We consider matroids with the property that every subset of the ground set of size t is contained in both an ℓ-element circuit and an ℓ-element cocircuit; we say that such a matroid has the (t, ℓ)-property. We show that for any positive integer t, there is a finite number of matroids with the (t, ℓ)-property for ℓ < 2t; however, matroids with the (t, 2t)-property form an infinite family. We say a matroid is a t-spike if there is a partition of the ground set into pairs such that the union of any t pairs is a circuit and a cocircuit. Our main result is that if a sufficiently large matroid has the (t, 2t)-property, then it is a t-spike. Finally, we present some properties of t-spikes.

AB - We consider matroids with the property that every subset of the ground set of size t is contained in both an ℓ-element circuit and an ℓ-element cocircuit; we say that such a matroid has the (t, ℓ)-property. We show that for any positive integer t, there is a finite number of matroids with the (t, ℓ)-property for ℓ < 2t; however, matroids with the (t, 2t)-property form an infinite family. We say a matroid is a t-spike if there is a partition of the ground set into pairs such that the union of any t pairs is a circuit and a cocircuit. Our main result is that if a sufficiently large matroid has the (t, 2t)-property, then it is a t-spike. Finally, we present some properties of t-spikes.

KW - Circuit

KW - Cocircuit

KW - Matroid

KW - Spike

UR - https://www.scopus.com/pages/publications/85064342704

U2 - 10.1137/18M1182255

DO - 10.1137/18M1182255

M3 - Article

AN - SCOPUS:85064342704

SN - 0895-4801

VL - 33

SP - 358

EP - 372

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

On a generalization of spikes

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this