6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Do you mean to be working with partial orders or pre-orders (since the latter is what you have actually defined)? $\endgroup$
    – Buzz
    Jul 22, 2021 at 1:49
  • $\begingroup$ @Buzz Oops, sorry. Fixed. Thanks for your attention. $\endgroup$ Jul 22, 2021 at 7:00
  • $\begingroup$ this "each pair participates in at most two swaps" reminds me this question mathoverflow.net/q/325477/4312 $\endgroup$ Jul 22, 2021 at 9:42

0

Your Answer

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

Browse other questions tagged or ask your own question.