1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Permutation graphs are perfect, therefore Lovasz theta, which is essentially a spectral bound, computes the clique number in polynomial time in polynomial time for this class of graphs.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – kvphxga Jul 17 '19 at 19:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Jul 17 '19 at 20:25
  • $\begingroup$ 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? $\endgroup$ – kvphxga Jul 17 '19 at 21:14
  • $\begingroup$ In practice noone runs the ellipsoid method (it's just the one for which the performance is understood well). $\endgroup$ – Dima Pasechnik Jul 17 '19 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.