Linear-sized independent sets in random cographs and increasing subsequences in separable permutations

DOI10.5070/C62359179zbMath1498.60040arXiv2104.07444WikidataQ125600646 ScholiaQ125600646MaRDI QIDQ5051470

Michael Drmota, Valentin Féray, Mathilde Bouvel, Frédérique Bassino, Adeline Pierrot, Lucas Gerin, Mickaël Maazoun

Publication date: 23 November 2022

Published in: Combinatorial Theory (Search for Journal in Brave)

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

zbMATH Keywords

self-similarity; random graphs; cographs; combinatorial probability; graphons; combinatorial graph theory

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05A05: Permutations, words, matrices

60C05: Combinatorial probability

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)