Skip to main content

Research Repository

Advanced Search

Combinatorial Representations

Cameron, Peter J.; Gadouleau, Maximilien; Riis, Søren

Combinatorial Representations Thumbnail


Authors

Peter J. Cameron

Søren Riis



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.

Citation

Cameron, P. J., Gadouleau, M., & Riis, S. (2013). Combinatorial Representations. Journal of Combinatorial Theory, Series A, 120(3), 671-682. https://doi.org/10.1016/j.jcta.2012.12.002

Journal Article Type Article
Publication Date Apr 1, 2013
Deposit Date Apr 10, 2013
Publicly Available Date Oct 19, 2015
Journal Journal of Combinatorial Theory, Series A
Print ISSN 0097-3165
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 120
Issue 3
Pages 671-682
DOI https://doi.org/10.1016/j.jcta.2012.12.002

Files





You might also like



Downloadable Citations