%0 Generic %1 shitov2024almost %A Shitov, Yaroslav %D 2024 %K binary boolean matrix monoid prime relation semigroup %R 10.13140/RG.2.2.28902.33603 %T Almost all Boolean matrices are prime %X Let B be a uniformly chosen random bipartite graph with two partition classes U and V of size n each. We prove that, asymptotically almost surely, if (G_1, . . . , G_n) is a family of complete bipartite subgraphs of B that covers all edges of B, then, either, each G_i has exactly one vertex in U, or each G_i has exactly one vertex in V. This answers a question of Kim and Roush from 1982 and leads to an asymptotically optimal bound for cardinalities of generating sets of the semigroup of all binary relations, which is a solution to a problem dating back to an article of Devadze from 1968.

@preprint{shitov2024almost, abstract = {Let B be a uniformly chosen random bipartite graph with two partition classes U and V of size n each. We prove that, asymptotically almost surely, if (G_1, . . . , G_n) is a family of complete bipartite subgraphs of B that covers all edges of B, then, either, each G_i has exactly one vertex in U, or each G_i has exactly one vertex in V. This answers a question of Kim and Roush from 1982 and leads to an asymptotically optimal bound for cardinalities of generating sets of the semigroup of all binary relations, which is a solution to a problem dating back to an article of Devadze from 1968.}, added-at = {2025-01-08T08:36:47.000+0100}, author = {Shitov, Yaroslav}, biburl = {https://www.bibsonomy.org/bibtex/2c990dcf47c89e3fa3b4bcb2b83ca0b23/jaeschke}, doi = {10.13140/RG.2.2.28902.33603}, interhash = {5a7853522e9150aaf7e09e964c81e310}, intrahash = {c990dcf47c89e3fa3b4bcb2b83ca0b23}, keywords = {binary boolean matrix monoid prime relation semigroup}, month = dec, timestamp = {2025-01-08T08:36:47.000+0100}, title = {Almost all Boolean matrices are prime}, year = 2024 }