# Spectral bound for maximum clique $k(G)$ in a permutation graph

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. 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.

• do you think Lovas theta function in this special case related to bound $max_{x\in S} \langle x, A x \rangle \ge \frac{1}{2}(1-\frac{1}{k(G)})$ on the simplex: $S = \{x\in[0,1]^n\colon \sum_i x_i =1\}$ given in the Motzkin and Straus paper? – kvphxga Jul 17 '19 at 19:22
• yes, these are related, as we showed in pure.uvt.nl/ws/portalfiles/portal/844532/approxim.pdf (see Lemma 5.2) - you get a slightly different function, $\theta'$, due to A.Schrijver, but they are the same for perfect graphs, IIRC. – Dima Pasechnik Jul 17 '19 at 20:25
• in case of the permutation adjacency matrix, can the SDP be approximated more efficiently than running Ellipsoid? How tight can the final value is related to the singular values of $A$? Maybe the result can be approximated by something like power iterations? – kvphxga Jul 17 '19 at 21:14