Skip to main content
MathOverflow

Return to Question

changed "twiddle" to "flip"
Source Link
edit approved Apr 18 at 7:30
jajangmyeon
edit approved Apr 18 at 7:30
jajangmyeon
  • 3
  • 1

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

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

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

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

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

Became Hot Network Question
Source Link
atenao
atenao
  • 333
  • 1
  • 5

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

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