The length of the longest increasing subsequence in a random permutation and the size of the largest homogeneous set (i.e. a clique or an independent set) in a random graph are two of the classical problems at the interface of combinatorics and probability theory, with connections to several other areas of mathematics.
In this paper, we investigated these classical problems in the setting of universal Brownian-type permutations and graphs, i.e. for the Brownian separable permutons and the Brownian cographons. These objects are the universal limits of various random permutations and graph families.
The diagram of three large permutations (in black) sampled from the Brownian separable permuton with parameter p=0.2,0.5,0.9 (from left to right). In red we highlighted one longest increasing subsequence.
The adjacency matrix of three large graphs (ones are plotted in black) sampled from the Brownian cographon with parameter p=0.2,0.5,0.9 (from left to right). In red we highlighted one largest homogeneous set. In the first two samples it is an independent set, while in the third case it is a clique.}
(1) A permutation of length 262144 sampled from the Brownian separable permuton of parameter p=1/2 with one longest increasing subsequence in red of length 22546. (2) The same permutation with one increasing subsequence of length 21751 in cyan computed using our selection rule to obtain the lower bound in the paper. (3-4) The two diagrams in (1) and (2) with only the two increasing subsequences. (5) The cyan increasing subsequence is plotted on top of the red increasing subsequence. Note that the two sequences are very similar since the cyan subsequence almost completely covers the red subsequence.
