5
$\begingroup$

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$?

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Apr 17 at 6:45
  • $\begingroup$ I guess you mean there are three ways to choose the two unfixed edges? I agree that eigenvalues are not needed. $\endgroup$
    – Tony Huynh
    Apr 17 at 7:34
  • $\begingroup$ there are three ways in total, but in an independent set at most one way $\endgroup$ Apr 17 at 7:50
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$) $\endgroup$ Apr 17 at 6:35
  • $\begingroup$ @FedorPetrov, Yes, my mistake. $\endgroup$
    – Peter Wu
    Apr 17 at 6:59
  • $\begingroup$ 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$. $\endgroup$
    – Tony Huynh
    Apr 17 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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