Let $\pi \in S_n$ be an arbitrary permutation. By permutation graph, we refer to a simple graph with nodes $[n]$ and edges that connect pairs of nodes that appear sorted in $\pi$. Formally, $G=(V=[n],E=\{\{i,j\}\colon i<j\;\&\; \pi_i<\pi_j\})$. It is clear from the definition that an increasing subsequence in $\pi$ would correspond to a clique in $G$. As a consequence maximum clique size $k(G)$ is equal to longest increasing subsequence (LIS) in the permutation $LIS(\pi)$. If $A$ denotes the adjacency matrix of $G$ (which is symmetric and transitive), question is: What can be said about spectral properties of $A$ and $LIS(\pi)$? The general clique problem is known to be NP-hard, but there some interesting spectral bounds, for instance: $$k(G)\ge \frac{n}{n-\lambda_1(A)}$$ derived using the theorem by Motzkin and Straus (link). but since we know that this specific problem has a dynamic programming solution, I am wondering if tighter bounds exist? Moroever, are there also upper bounds for $k(G)$?
This might seem like formulating an easy problem by a much harder one, but for reasons not discussed here, the spectral properties of permutation graph are of interest.
