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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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$.

Improve this answer
$\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$
    – Fedor Petrov
    Commented 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
    Commented Apr 17 at 7:34
  • $\begingroup$ there are three ways in total, but in an independent set at most one way $\endgroup$
    – Fedor Petrov
    Commented 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.

Improve this answer
$\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$
    – Fedor Petrov
    Commented Apr 17 at 6:35
  • $\begingroup$ @FedorPetrov, Yes, my mistake. $\endgroup$
    – Peter Wu
    Commented 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
    Commented Apr 17 at 7:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .