We study visualizations of attractors, which occur in chaotic dynamic systems, and for a few years trying to prove or refute Conjecture [3]. It has an equivalent formulation in terms of order theory, see below.
Let $n$ be a natural number and $[n]=\{1,\dots, n\}$. Recall that a partial order $P $ on a set $[n]$ is a subset of $[n]\times [n]$ and its dimension $\operatorname{dim} P$ is the minimal size of a family $\mathcal L$ of linear orders on $[n]$ such that $P =\bigcap\mathcal L$. It is known that a tight upper bound on the dimension of a $P$ is $\lfloor n/2\rfloor$ for $n \ge 4$, see [1, Section 8].
A “ smooth” representation of $P$ can be provided by the following
Conjecture. For any natural $n$, any partial order $P$ on $[n]$, and any linear order $L_0\supset P$ on $[n]$ there exists a slowly changing cyclic sequence $\{L_0,\dots, L_k, L_{k+1}=L_0\}$ of linear orders on $[n]$ such that $P=\bigcap_{m=0}^{k+1} L_m$.
"Slowly changing" means the following:
1)) For each $m=0,\dots, k$, $|L_m\Delta L_{m+1}|=2$. Since both $L_m$ and $L_{m+1}$ are linear orders, this condition is equivalent to $L_{m+1}=L_{m}\cup \{(j,i)\}\setminus \{(i,j)\}$ for some $(i, j)\in L_m$. We say that the order $L_{m+1}$ is obtained from an order $L_m$ by a (unique) swap of elements $i,j$. Also note, that since $L_m$ is a linear order then $L_{m}\cup \{(j,i)\}\setminus \{(i,j)\}$ is a partial (or a linear) order iff there is no $k\in [n]\setminus\{i,j\}$ such that both $(i,k)$ and $(k,j)$ belong to $L_m$. So, for instance, for $n=4$, the order $1<2<3<4$ can precede orders $2<’1<’3<’4$, $1<’’3<’’2<’’4$, and $1<’’’2<’’’4<’’’3$.
2)) Each pair of distinct elements of $[n]$ participates in at most $2$ swaps mentioned in (1).
Our try. We can prove Conjecture when $P$ is an intersection of a family $\mathcal L$ of linear orders on $[n]$ such that $L\cap L’\subset L_0$ for each distinct elements $L,L’\in\mathcal L$.
Moreover, without loss of generality we can assume that $L_0$ is the usual linear order on $[n]$ and $P\subset L_0$. Computer calculations verified the conjecture for all $n\le 8$. But the number of partial orders $P\subset L_0\subset [n]\times [n]$ increases drastically with increasing $n$ and for $n=9$ there are more than $10^8$ partial orders to check. So for $9 \le n \le 60$ we generated by three different methods more than $10^5$ random $P$, by found no counterexample to Conjecture.
So we tried to prove a conjecture with the number $2$ in (2) relaxed to some $f(n)$. In Lemma 4 from [3] is used the following idea. Given $P$, there exists a sequence $(L’_1,\dots, L’_d)$ of length $d=\operatorname{dim} P$ of linear orders on $[n]$ such that $P =\bigcap_{m=1}^d L’_m$. Modifying a bit a construction from Lemma 4, we can extend $(L’_1,\dots, L’_d)$ to a required sequence $(L_0, L_1,\dots, L_{k+1})$, satisfying $f(n)=d+1\le n/2+1$ for $n\ge 4$. I expect I can improve this bound to $f(n)=d/2+o(n)$ by a suitable reenumeration of the sequence $(L’_1,\dots, L’_d)$, assuring that for each pair $(i,j)$ of distinct elements of $[n]$ there is at most $d/2+o(n)$ indices $m\in [d-1]$ such that $(i,j)\in L’_m$ iff $(j,i)\in L’_{m+1}$. But the needed estimations for this bound look rather complicated, like those used in the probabilistic method [2].
Thanks.
Update. We can reduce Conjecture to partial orders of rather simple structure. The reduction looks so promising that I posed the reduced problem to our students. Namely, recall that an alternative definition of order dimension of a partial order $P$ is the minimal number of linear orders such that $P$ embeds into their product with componentwise ordering i.e. $x \le y$ iff $x_i \le y_i$ for all $i$. Since the "removal" of elements of $[n]$ from a “smooth” representation keeps its “smoothness”, we need to check Conjecture only for partial orders $P$ of the form $(1<2<...<k)^d$ for some natural $k$ and $d$. Or only the discrete simplexes of the set $[k]^d$, constituted of a union of “layers” $M_i=\{(x_1,...x_d)\in [k]^d: x_1+...+x_d=i\}$, $d\le i\le k$ of pairwise incomparable elements. Maybe the reduced conjecture can be easily proved by induction with respect to $k$ (or $d$?). Anyway, the case $d=2$ looks to be a good start. Note that to simplify the investigation, we initially can relax the condition “any linear order $L_0\supset P$” to “some linear order $L_0\supset P$”, because it will cost up only at most two additional swaps for each pair of elements, that is the relaxed reduced conjecture provides a bound $f(n)\le 4$ for each $n$.
References
[1] Hiraguchi T., On the dimension of orders, Sci. rep. Kanazawa univ. 4:1 (1955) 1–20.
[2] Spencer J., Ten lectures on the probabilistic method, 2nd edn. CBMS-NSF Regional conference series in applied mathematics, 64, SIAM, 1994.
[3] Firman O., Kindermann P., Ravsky A., Wolff A., Zink J., Computing optimal tangles faster, In: Eds. Löffler M. Proc. 35th European workshop on computational geometry 61 (2019), 1–7.