We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Combinatorial representations.

Cameron, Peter J. and Gadouleau, Maximilien and Riis, Søren (2013) 'Combinatorial representations.', Journal of combinatorial theory. Series A., 120 (3). pp. 671-682.


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
Publisher Web site:
Publisher statement:© 2012 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
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

Look up in GoogleScholar