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][1]).
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. 


  [1]: https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maxima-for-graphs-and-a-new-proof-of-a-theorem-of-turan/AC3CC45896B053B75C856F25829CA95C