Random GF(q)-representable matroids are not (b,c)-decomposable

arXiv2208.05464MaRDI QIDQ6407536FDOQ6407536

Authors: J. G. van der Pol 

Publication date: 10 August 2022

Abstract: We show that a random subset of the rank-$n$ projective geometry $extPG(n-1,q)$ is, with high probability, not $(b,c)$-decomposable: if $k$ is its colouring number, it does not admit a partition of its ground set into classes of size at most $ck$, every transversal of which is $b$-colourable. This generalises recent results by Abdolazimi, Karlin, Klein, and Oveis Gharan (arXiv:2111.12436) and by Leichter, Moseley, and Pruhs (arXiv:2206.12896), who showed that $extPG(n-1,q)$ is not $(1,c)$-decomposable, resp. not $(b,c)$-decomposable.

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

This page was built for publication: Random GF(q)-representable matroids are not (b,c)-decomposable

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