Combinatorial representations

DOI10.1016/J.JCTA.2012.12.002MaRDI QIDQ1940378zbMATH OpenOpenAlexFDO

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

Publication date 6 March 2013

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.1216

zbMATH Keywords

entropymatroidsorthogonal Latin squaresWilson's theorem

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of matroids and geometric lattices (05B35)

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 rank 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.

Recommendations

• Publication:3484842
• Combinatorial generation of matroid representations: theory and practice
• Hall ratio of the Mycielski graphs
• scientific article; zbMATH DE number 3880730
• scientific article; zbMATH DE number 4039924

Cited in

(7)

• Decision systems in rough set theory: a set operatorial perspective
• Combinatorial Characters
• scientific article; zbMATH DE number 7145391 (Why is no real title available?)
• Memoryless computation: new results, constructions, and extensions
• Counting common representatives and symmetric chain decompositions
• scientific article; zbMATH DE number 4156447 (Why is no real title available?)
• Interleavings and matchings as representations

This page was built for publication: Combinatorial representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1940378)