2
$\begingroup$

Let $G=(V,E)$ be a complete graph $K_{2n}$ and it has $m$ 1-factors $f_{i,(i=1,\dots,m)}$, where $m=\frac{(2n)!}{n!2^n}$.

Some definition:

  • $F=\{f_{1},f_{2},...,f_{2n-1}\}$ is one 1-factorization in $K_{2n}$.
  • $S(F)$ is the number of 1-factors in one $F$; and $S(F)=2n-1$.
  • $N(F)$ is the number of distinct 1-factorizations in $K_{2n}$;
    • If $N(F)=k$, we use $F_{1}$,$F_{2}$,...,$F_{k}$ to indicate distinct $F$ .
    • For $K_{2n}$, when $n=1,2,3,4$, we know $N(F)=1,1,6,6240$; see A000438.

For each $f_{i}$ in $K_{2n}$, we label the edges of $f_{i}$ with numbers 1,2,...,(2n-1). For each $f_{i}$ in $F$, none of them are labeled with the same number (which means disjoint 1-factors).

Now we associate with vertex $v$ in $K_{2n}$ with a word (not number) $r$ such that $r$ is the label of the edge incident with $v$ in $f_{i}$ of $K_{2n}$. It's straightforward to check that the resulting code {$r,v\in V$} has desired parameter from $1,2,...,(2n-1)$. We label the coded word in one $f_{i}$ as $W(f_{i})=r_{1}r_{2}...r_{2n}$ (corresponding to the sequence arrangement as $v_{1}v_{2}...v_{2n}$).

see the following two examples for description:

$f_{x}=\{(v_{1}v_{4}),(v_{2}v_{6}),(v_{3}v_{5})\}=\{(11),(22),(33)\}$ : $W(f_{x})=r_{1}r_{2}...r_{6}=123132$ $f_{x}=\{(v_{1}v_{6}),(v_{2}v_{5}),(v_{3}v_{4})\}=\{(22),(44),(55)\}$ : $W(f_{x})=r_{1}r_{2}...r_{6}=245542$


We separate $m$ 1-factors $f_{i}$ into two groups:

  • group1: {$f_{i|i=1,2,...,2n-1}$} which forms $F$ (disjoint 1-factors in $K_{2n}$)
  • group2: {$f_{i|i=2n,2n+1,...,m}$} which forms $F'$ (remaining 1-factors in $K_{2n}$)

They form two polynomials: $Y(F)=\sum_{i=1}^{(2n-1)} W(f_{i})$ and $Y(F')=\sum_{i=2n}^m W(f_{i})$. Thus there will be $N(F)$ cases for $Y(F')$, which we can use $Y(F')_{1}$, $Y(F')_{2}$, ..., $Y(F')_{N(F)}$to indicate.

Question:

For 1-factorization $F$, one can permute the numbers from ($1,2,...,2n-1$) to label each $f_{i}$ in $F$, thus there will be $(2n-1)!$ label settings. In addition, there are in total $N(F)$ 1-factorizations in $K_{2n}$. Therefore we know there will be $t=N(F)*(2n-1)!$ cases for $Y(F')$.

$\exists i,j\in [1,t]$ and $i\not\equiv j$, $Y(F')_{i}==Y(F')_{j}$?

$\endgroup$

0

Your Answer

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