5
$\begingroup$

Let $a_1a_2\ldots a_{2n+1}$ ($n\geq 2$) be a given permutation of the numbers from $1$ to $2n+1$ and let

  • $\alpha_i=\{i,i+1,i+2\},~1\leq i\leq 2n-1$
  • $\alpha_{2n}=\{2n,2n+1,1\}$
  • $\alpha_{2n+1}=\{2n+1,1,2\}$
  • $\beta_i=\{a_i,a_{i+1},a_{i+2}\},~1\leq i\leq 2n-1$
  • $\beta_{2n}=\{a_{2n},a_{2n+1},a_1\}$
  • $\beta_{2n+1}=\{a_{2n+1},a_{1},a_2\}$.

Can we find two sets $A,B\subset \{1,2,\ldots,2n+1\}$ such that

  • $\alpha_i\not\subseteq A$ for each $1\leq i\leq 2n+1$,
  • $\beta_i\not\subseteq B$ for each $i\leq i\leq 2n+1$,
  • $A\cup B=\{1,2,\ldots,2n+1\}$?

Welcome any valuable answer or idea on this question. Thanks in advance.

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ In others words for any permutation $\pi$ of $X = \mathbb{Z}/m\mathbb{Z}$ find some $A\subset X$ such that $\{i,i+1,i+2\}\cap (X\setminus A) \ne \emptyset$ and $\{\pi(i),\pi(i+1),\pi(i+2)\}\cap A \ne \emptyset$ for all $i\in X$, where $m=2n+1$? $\endgroup$
    – Claude Chaunier
    Commented Apr 25 at 9:23
  • $\begingroup$ please clarify if the comment above expresses the question correctly $\endgroup$
    – kodlu
    Commented Apr 25 at 15:32
  • 1
    $\begingroup$ The original question may require there are no three consecutive elements of X in X\A, and meanwhile there are no three consecutive elements of π(X) in A. $\endgroup$
    – Xin Zhang
    Commented Apr 26 at 1:27
  • $\begingroup$ I agree wth the 3rd comment of Xin. Following the notations given by Claude above , if m=7, then we put 2,5,6 into A. Then, 0,1,3,4 are in X\A, and there are now no three consective numbers in the cyclic permutation 0123456. If we fail in this way, then 2,5,6 must be three consective numbers in $\pi(X)$ (note that the partial sequence in $\pi(X)$ may be 256 or 265 or 526 or..... ). Similarly, 2+i,5+i,6+i (mod 7) are three consective numbers in $\pi(X)$. Now 256, 512, 623 are three consective numbers in $\pi(X)$, but it is impossible. This proves for $m=7$. How can I go further? $\endgroup$
    – W. Paul Liu
    Commented Apr 26 at 4:19
  • 1
    $\begingroup$ @Max Alekseyev Why $p=(1,3,5,2,4)$ is a conterexample? In my original question, I can choose {1,3,4} for $A$ and {2,5} for $B$. $\endgroup$
    – W. Paul Liu
    Commented Apr 26 at 13:13

1 Answer 1

Reset to default
3
$\begingroup$

The answer is Yes.

Let me first reformulate the problem. For a given permutation $(a_1,a_2,\dots,a_{2n+1})$, we construct a 2-colored graph $G$ on vertices $[2n+1]:=\{1,2,\dots,2n+1\}$ formed by black edges $\{i,i+1\}$ and gray edges $\{a_i,a_{i+1}\}$ for $i\in [2n+1]$ with $2n+2\equiv 1$. Hence, $G$ is the superposition of the black and gray cycles, each of length $2n+1$. The question is equivalent to finding a labeling of the vertices of $G$ with labels from $\{A,B\}$, imposing the edge labels from $\{AA,AB,BB\}$ formed by the labels of edge's endpoints, such that there are no two adjacent black edges both labeled $AA$, and there are no two adjacent gray edges both labeled $BB$. We call such pairs of adjacent labeled edges forbidden.

Let us show that the required labeling exists for any $n\geq 2$.

We construct graph $G'$ from $G$ by first removing vertex $1$ with its incident edges, which we refer to as special. Then we further remove black edges $\{3,4\}$, $\{5,6\}$, ..., $\{2n-1,2n\}$, and gray edges $\{a_{s+2},a_{s+3}\}$, $\{s_{s+4},a_{s+5}\}$, ..., $\{a_{s+2n-2},a_{s+2n-1}\}$, where $s:=a^{-1}(1)$, i.e. $a_s=1$. In other words, we remove every other edge along the black path and every other edge along the gray path. We refer to these removed edges as bridges in $G$, and to the remaining edges (i.e., the edges in $G'$) as basic.

In the graph $G'$, every vertex is incident to one black and one gray edge, and so $G'$ is the disjoint union of alternating cycles of even length. We label vertices along each such cycle alternatively with $A$'s and $B$'s starting at an arbitrary vertex, except for the cycle containing vertex $2$, in which we start with vertex $2$ labeling it with $B$. Hence, all edges of $G'$ inherit label $AB$ from their endpoints. We propagate the vertex labeling from $G'$ to $G$, additionally labeling vertex $1$ with $A$.

Each basic edge in $G$ has label $AB$ and thus it cannot participate in a forbidden pair. So, if a forbidden pair exists, it is formed by bridges and/or special edges. However, a bridge $e$ cannot participate in a forbidden pair since its adjacent edges of the same color as $e$ are basic. It remains to notice that two special edges cannot form a forbidden pair either, since the black special edge $(1,2)$ has label $AB$, while the labels of gray special edges are either $AA$ or $AB$ (since vertex $1$ has label $A$). QED

PS. Graphs like $G$ are known under the name of (unsigned) breakpoint graphs.

Improve this answer
$\endgroup$

You must log in to answer this question.

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