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](https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maxima-for-graphs-and-a-new-proof-of-a-theorem-of-turan/AC3CC45896B053B75C856F25829CA95C)).
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. 



Spectral bound for maximum clique $k(G)$ in a permutation graph
[Permutation graphs](https://en.wikipedia.org/wiki/Permutation_graph) are perfect, therefore [Lovasz theta](https://en.wikipedia.org/wiki/Lov%C3%A1sz_number), which is essentially a spectral bound, computes the clique number in polynomial time in polynomial time for this class of graphs.


