# Independence number of configuration graph (consisting of all (2k-1)!! ways to partition {1,2,...,2k} into k pairs)

Let $$k$$ be a nonnegative integer. A configuration on $$2k$$ labeled points is simply a partition of the points into $$k$$ pairs, so for any set of $$2k$$ labeled points, there are $$(2k-1)!!$$ configurations.

We construct the configuration graph $$G_k$$, by saying that two configurations $$A$$ and $$B$$ are adjacent if $$A$$ can be turned into $$B$$ by doing a flip (changing two pairs $$\{a,b\},\{c,d\}$$ to $$\{a,c\},\{b,d\}$$). Explicitly, we say that $$A$$ and $$B$$ are adjacent if $$A$$ consists of pairs $$\{a,b\}, \{c,d\}, \{x_5,x_6\}, \{x_7,x_8\}, \dots, \{x_{2k-1},x_{2k}\}$$ and $$B$$ consists of pairs $$\{a,c\},\{b,d\},\{x_5,x_6\}, \{x_7,x_8\}, \dots, \{x_{2k-1},x_{2k}\}$$, for some way of assigning labels $$a,b,c,d,x_5,x_6,x_7,x_8,\dots,x_{2k-1},x_{2k}$$.

For instance, when $$k=2$$, the configuration graph $$G_2$$ is simply $$K_3$$; there are three configurations on $$2k=4$$ points, and each configuration is related to the others via a flip.

I'm interested in bounds for the independence number $$\alpha(G_k)$$. In particular, is it true that the independence number is a $$o(1)$$ fraction of the total number of vertices of $$G_k$$?

Here are some upper and lower bounds.

The paper On the chromatic number of some flip graphs proves that the chromatic number of $$G_k$$ is at most $$4k-4$$. Therefore, in every proper colouring of $$G_k$$ there must be a colour class of size at least $$\frac{(2k-1)!!}{4k-4}$$. Thus, $$\alpha(G_k) \geq \frac{(2k-1)!!}{4k-4}$$.

On the other hand, the eigenvalues of $$G_k$$ are well-known and using the Hoffman Ratio Bound, we obtain $$\alpha(G_k) \leq \frac{(2k-1)!!}{3}$$.

Better bounds are known for small values of $$k$$. For example, at the end of the paper On the flip graphs on perfect matchings of the complete graphs and signed reversal graphs, they note that $$\alpha(G_4)=28$$ and $$\alpha(G_5) \geq 208$$.

• The one-third bound is clear without eigenvalues: if we fix all edges except 2, we have at most one way to choose these 2. The same trick proves that $\alpha(G_k) /(2k-1)!!$ decreases Apr 17 at 6:45
• I guess you mean there are three ways to choose the two unfixed edges? I agree that eigenvalues are not needed. Apr 17 at 7:34
• there are three ways in total, but in an independent set at most one way Apr 17 at 7:50

Here is a construction with $$\Omega(1/k)$$ fraction: consider $$x_1x_2+x_3x_4+\dots \mod p$$. In which $$p$$ is a prime larger than $$k$$. If two vertices are adjacent, their difference is $$(b-c)(a-d)$$, which is not divided by $$p$$. Thus one can take the largest residue class.

• You mean, $\Omega(1/k)$, not $o(1/k)$? (an example is interesting if it has many vertices, so $p$ should be chosen the smallest prime larger than $k$) Apr 17 at 6:35
• @FedorPetrov, Yes, my mistake. Apr 17 at 6:59
• The second paper linked to in my answer proves that if $q$ is the smallest prime power larger than $2k$, then the chromatic number of $G_k$ is at most $q$. Apr 17 at 7:15