Cameron, Peter J. and Gadouleau, Maximilien and Riis, Søren (2013) 'Combinatorial representations.', Journal of combinatorial theory. Series A., 120 (3). pp. 671-682.
Abstract
This paper introduces combinatorial representations, which generalise the notion of linear representations of matroids. We show that any family of subsets of the same cardinality has a combinatorial representation via matrices. We then prove that any graph is representable over all alphabets of size larger than some number depending on the graph. We also provide a characterisation of families representable over a given alphabet. Then, we associate a rank function and a closure operator to any representation which help us determine some criteria for the functions used in a representation. While linearly representable matroids can be viewed as having representations via matrices with only one row, we conclude this paper by an investigation of representations via matrices with only two rows.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution Non-commercial No Derivatives. Download PDF (309Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1016/j.jcta.2012.12.002 |
| Publisher statement: | © 2012 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Date accepted: | No date available |
| Date deposited: | 19 October 2015 |
| Date of first online publication: | April 2013 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
