2022/08/10 by Jorn van der Pol, van der Pol, Jorn
Computer Science · Mathematics · #05B35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2208.05464
openalex publication_date 2022/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that a random subset of the rank-n projective geometry PG(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 PG(n-1,q) is not (1,c)-decomposable, resp. not (b,c)-decomposable.