Peter J. Cameron
Combinatorial Representations
Cameron, Peter J.; Gadouleau, Maximilien; Riis, Søren
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.
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 |
Public URL | https://durham-repository.worktribe.com/output/1456395 |
Files
Accepted Journal Article
(316 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright 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/
You might also like
On Finite Monoids of Cellular Automata
(2016)
Presentation / Conference Contribution
Generalizing Bounds on the Minimum Distance of Cyclic Codes Using Cyclic Product Codes
(2013)
Presentation / Conference Contribution
Max-Flow Min-Cut Theorem for Rényi Entropy in Communication Networks
(2011)
Presentation / Conference Contribution
Packing and Covering Properties of Subspace Codes
(2009)
Presentation / Conference Contribution
Network Coding Theorem for Dynamic Communication Networks
(2011)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search